Được vinh dự trở thành thí sinh tham dự vòng chung kết ICPC toàn cầu, Ami không giấu nổi niềm kiêu hãnh hiếm hoi mà cậu có được trong năm đầu của đời sinh viên. Ami liên tục up ảnh khoe mẽ lên Facebook, Instagram, Twitter, Lotus, etc - phủ sóng mọi nơi mà cuom1999 có thể nhìn thấy trong lúc lướt web giải trí. Quá chướng mắt với sự khủng bố tinh thần từ ami, cuom1999 đã lên một kế hoạch thâm độc để trả thù: cưa đổ người tình Xiêm La LN của ami.
Sau khi lân la kết bạn dò hỏi, cuom1999 biết được rằng cứ mỗi ngày rằm trong bốn tháng trời yêu xa, ami đều sử dụng dịch vụ chuyển phát nhanh theo tuyến Texas - Bangkok để gửi cho LN một dãy bit nhị phân độ dài N. Bốn dãy bit được LN xem như là những kỷ vật tình yêu vô giá và cô đã lần lượt ký hiệu chúng là A, B, C và D. Tuy nhiên, một chuyên gia khoa học máy tính như cuom1999 đã quá quen thuộc với những con số nhị phân nên cậu tỏ ý xem thường những dãy bit này của LN. LN vừa cảm thấy bị xúc phạm thay cho ami, vừa muốn đập tan thái độ kiêu ngạo của cuom1999 nên đã viết ra một biểu thức tình yêu cực kỳ phức tạp để thách thức cuom1999 tính toán được kết quả của nó. Một biểu thức tình yêu sẽ có dạng (X opt Y), trong đó:
- X và Y là những biểu thức tình yêu khác hoặc ký hiệu cho một trong bốn dãy bit trên.
- opt là một trong ba ký hiệu '|', '&' và '^' - tượng trưng lần lượt cho ba toán tử logic or, and và xor.
LN hứa sẽ hẹn hò với cuom1999 nếu cậu tính ra được dãy bit kết quả của biểu thức tình yêu này. Nhưng không may, biểu thức lại quá phức tạp còn cuom1999 lại đang vùi đầu vào ôn thi môn Network nên đành nhờ đến bạn. Bạn hãy giúp cuom1999 đập chậu cướp hoa nhé!
Định dạng input:
- Dòng đầu chứa số nguyên dương N thể hiện độ dài của 4 dãy bit.
- 4 dòng tiếp theo lần lượt thể hiện giá trị của dãy bit A, B, C và D.
- Dòng cuối chứa một xâu ký tự thể hiện biểu thức tình yêu cần tính. Biểu thức có định dạng chuẩn như đề bài mô tả và không chứa dấu cách nào.
Định dạng output:
- Một dòng duy nhất là dãy bit kết quả.
Ràng buộc:
- N ≤ 106.
- Có tối đa 105 toán tử trong biểu thức cần tính.
Giải thích:
- A & B = 1110 & 0110 = 0110.
- C | D = 1001 | 0110 = 1111.
- (A & B) ^ (C | D) = 0110 ^ 1111 = 1001.