{"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 $ n \\in \\mathbb{Z} $ be the number of commands in Petya’s program.  \nLet $ C = \\{(op_i, x_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the sequence of commands, where $ op_i \\in \\{\\&, |, \\oplus\\} $ and $ x_i \\in \\{0, 1, \\dots, 1023\\} $.  \n\nLet $ f: \\{0, 1, \\dots, 1023\\} \\to \\{0, 1, \\dots, 1023\\} $ be the function computed by Petya’s program:  \n$$ f(x) = op_n(x_n, op_{n-1}(x_{n-1}, \\dots op_1(x_1, x) \\dots )) $$  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 5 \\cdot 10^5 $  \n2. $ 0 \\leq x_i \\leq 1023 $ for all $ i $  \n\n**Objective**  \nFind a program with $ k \\leq 5 $ commands $ \\{(op'_j, x'_j) \\mid j \\in \\{1, \\dots, k\\}\\} $ such that for all $ x \\in \\{0, 1, \\dots, 1023\\} $:  \n$$ f(x) = op'_k(x'_k, op'_{k-1}(x'_{k-1}, \\dots op'_1(x'_1, x) \\dots )) $$  \n\nMoreover, since all operations are bitwise and constants are 10-bit, the function $ f $ is equivalent to:  \n$$ f(x) = (x \\mathbin{\\text{op}_1} x_1) \\mathbin{\\text{op}_2} x_2 \\mathbin{\\text{op}_3} \\dots \\mathbin{\\text{op}_n} x_n $$  \nand due to the linearity and idempotence properties of bitwise operations, $ f(x) $ can be rewritten as:  \n$$ f(x) = (x \\& A) | (B) \\oplus (C) $$  \nfor some constants $ A, B, C \\in \\{0, 1, \\dots, 1023\\} $, computable by evaluating $ f $ on three basis inputs: $ x = 0 $, $ x = 1023 $, and $ x = 1 \\ll i $ for each bit $ i \\in \\{0, \\dots, 9\\} $.  \n\nWe can compress any sequence of AND, OR, XOR operations into at most 3 operations:  \n$$ f(x) = ((x \\& A) \\mid B) \\oplus C $$  \nand further reduce to at most 5 operations if needed, but optimally to 3.  \n\nThus, compute constants $ A, B, C $ such that:  \n- $ A $: bits preserved (AND mask)  \n- $ B $: bits forced to 1 (OR mask)  \n- $ C $: bits flipped (XOR mask)  \n\nThen output the minimal sequence of up to 5 operations that implements $ f(x) = ((x \\& A) | B) \\oplus C $, using at most one of each operation type, in optimal order.  \n\n**Output**  \nFind $ k \\in \\{0, 1, 2, 3, 4, 5\\} $ and $ k $ commands minimizing the program length while preserving $ f(x) $ for all $ x \\in [0, 1023] $.","simple_statement":null,"has_page_source":false}