{"raw_statement":[{"iden":"statement","content":"Petya learned a new programming language CALPAS. A program in this language always takes one non-negative integer and returns one non-negative integer as well.\n\nIn the language, there are only three commands: apply a bitwise operation AND, OR or XOR with a given constant to the current integer. A program can contain an arbitrary sequence of these operations with arbitrary constants from 0 to 1023. When the program is run, all operations are applied (in the given order) to the argument and in the end the result integer is returned.\n\nPetya wrote a program in this language, but it turned out to be too long. Write a program in CALPAS that does the same thing as the Petya's program, and consists of no more than 5 lines. Your program should return the same integer as Petya's program for all arguments from 0 to 1023."},{"iden":"input","content":"The first line contains an integer _n_ (1 ≤ _n_ ≤ 5·105) — the number of lines.\n\nNext _n_ lines contain commands. A command consists of a character that represents the operation (\"_&_\", \"_|_\" or \"_^_\" for AND, OR or XOR respectively), and the constant _x__i_ 0 ≤ _x__i_ ≤ 1023."},{"iden":"output","content":"Output an integer _k_ (0 ≤ _k_ ≤ 5) — the length of your program.\n\nNext _k_ lines must contain commands in the same format as in the input."},{"iden":"examples","content":"Input\n\n3\n| 3\n^ 2\n| 1\n\nOutput\n\n2\n| 3\n^ 2\n\nInput\n\n3\n& 1\n& 3\n& 5\n\nOutput\n\n1\n& 1\n\nInput\n\n3\n^ 1\n^ 2\n^ 3\n\nOutput\n\n0"},{"iden":"note","content":"You can read about bitwise operations in [https://en.wikipedia.org/wiki/Bitwise_operation](https://en.wikipedia.org/wiki/Bitwise_operation).\n\nSecond sample:\n\nLet _x_ be an input of the Petya's program. It's output is ((_x_&1)&3)&5 = _x_&(1&3&5) = _x_&1. So these two programs always give the same outputs."}],"translated_statement":[{"iden":"statement","content":"Petya 学习了一种新的编程语言 CALPAS。这种语言的程序总是接受一个非负整数，并返回一个非负整数。\n\n该语言中只有三种指令：将给定的常数与当前整数进行按位与（AND）、或（OR）或异或（XOR）操作。程序可以包含任意数量的这些操作，常数范围为 #cf_span[0] 到 #cf_span[1023]。当程序运行时，所有操作按给定顺序依次应用于输入整数，最终返回结果整数。\n\nPetya 编写了一个该语言的程序，但程序过长。请编写一个 CALPAS 程序，其功能与 Petya 的程序完全相同，且指令行数不超过 #cf_span[5] 行。你的程序对所有从 #cf_span[0] 到 #cf_span[1023] 的输入，必须返回与 Petya 程序相同的整数。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) —— 表示指令行数。\n\n接下来 #cf_span[n] 行为指令。每条指令由一个表示操作的字符（\"_&_\"、\"_|_\" 或 \"_^_\" 分别代表 AND、OR 或 XOR）和一个常数 #cf_span[xi] (#cf_span[0 ≤ xi ≤ 1023]) 组成。\n\n请输出一个整数 #cf_span[k] (#cf_span[0 ≤ k ≤ 5]) —— 你的程序的长度。\n\n接下来 #cf_span[k] 行必须以与输入相同的格式输出指令。\n\n你可以阅读关于按位操作的更多信息：https://en.wikipedia.org/wiki/Bitwise_operation。\n\n第二个样例：\n\n设 #cf_span[x] 为 Petya 程序的输入，其输出为 #cf_span[((x&1)&3)&5 = x&(1&3&5) = x&1]。因此这两个程序对所有输入均产生相同结果。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) —— 表示指令行数。接下来 #cf_span[n] 行为指令。每条指令由一个表示操作的字符（\"_&_\"、\"_|_\" 或 \"_^_\" 分别代表 AND、OR 或 XOR）和一个常数 #cf_span[xi] (#cf_span[0 ≤ xi ≤ 1023]) 组成。"},{"iden":"output","content":"请输出一个整数 #cf_span[k] (#cf_span[0 ≤ k ≤ 5]) —— 你的程序的长度。接下来 #cf_span[k] 行必须以与输入相同的格式输出指令。"},{"iden":"examples","content":"输入3| 3^ 2| 1输出2| 3^ 2输入3& 1& 3& 5输出1& 1输入3^ 1^ 2^ 3输出0"},{"iden":"note","content":"你可以阅读关于按位操作的更多信息：https://en.wikipedia.org/wiki/Bitwise_operation。第二个样例：设 #cf_span[x] 为 Petya 程序的输入，其输出为 #cf_span[((x&1)&3)&5 = x&(1&3&5) = x&1]。因此这两个程序对所有输入均产生相同结果。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**\nLet $\\mathcal{D} = \\{ z \\in \\mathbb{Z} \\mid 0 \\le z \\le 1023 \\}$ be the domain of 10-bit non-negative integers.\nLet $\\Omega = \\{ \\&, |, \\oplus \\}$ be the set of bitwise operations (AND, OR, XOR).\nA command is a tuple $(\\diamond, c)$ where $\\diamond \\in \\Omega$ and $c \\in \\mathcal{D}$.\n\n**Given**\n1.  An integer $n$ where $1 \\le n \\le 5 \\cdot 10^5$.\n2.  A sequence of commands $S = \\langle (\\diamond_1, c_1), (\\diamond_2, c_2), \\dots, (\\diamond_n, c_n) \\rangle$.\n\n**Function Definition**\nLet $f_S: \\mathcal{D} \\to \\mathcal{D}$ be the function defined by the sequential application of $S$ on an input $x \\in \\mathcal{D}$.\nLet $y_0 = x$.\nFor $i = 1, \\dots, n$, let $y_i = y_{i-1} \\diamond_i c_i$.\nThen $f_S(x) = y_n$.\n\n**Objective**\nFind a sequence of commands $S' = \\langle (\\diamond'_1, c'_1), \\dots, (\\diamond'_k, c'_k) \\rangle$ satisfying the following conditions:\n1.  $0 \\le k \\le 5$.\n2.  $\\forall x \\in \\mathcal{D}, f_{S'}(x) = f_S(x)$.\n\n**Output**\n1.  The integer $k$.\n2.  The sequence $S'$ formatted as $k$ lines, each containing the character representation of $\\diamond'_j$ and the integer $c'_j$.","simple_statement":null,"has_page_source":false}