{"raw_statement":[{"iden":"statement","content":"Let us denote $\"mex\"(a, b)$ (minimum excludant) as the minimum non-negative integer which is neither equal to $a$ nor equal to $b$. It always holds that $\"mex\"(a, b) < 3$, thus we can define tritwise mex. If we write $a$ and $b$ in ternary notation: $$a = \\sum\\limits_{i=0}^{k-1}a_i \\cdot 3^i,~~b=\\sum\\limits_{i=0}^{k-1} b_i \\cdot 3^i\\text{,}$$ where $a_i$ and $b_i$ are integers from $0$ to $2$, we define $upright(m e x)_3$ as follows: $$\\mathrm{mex}_3(a, b) = \\sum\\limits_{i=0}^{k-1}\\mathrm{mex}(a_i,b_i) \\cdot 3^i\\text{.}$$ You are given two sequences $a_0, \\\\dots, a_(3^k -1)$ and $b_0, \\\\dots, b_(3^k -1)$. You have to compute the sequence $c_0, \\\\dots, c_(3^k -1)$: $$c_k = \\sum\\limits_{\\mathrm{mex}_3(i,j)=k}a_i \\cdot b_j\\text{.}$$\n\nThe first line of input contains a single integer $k$ ($1 <= k <= 12$).\n\nThe second line of input contains $3^k$ integers $a_0, \\\\dots, a_(3^k -1)$ ($0 <= a_i <= 10^3$).\n\nThe third line of input contains $3^k$ integers $b_0, \\\\dots, b_(3^k -1)$ ($0 <= b_i <= 10^3$).\n\nOutput $3^k$ integers $c_0, \\\\dots, c_(3^k -1)$ separated by spaces.\n\nFor reference: $3^(12) = 531 thin 441$.\n\n"},{"iden":"input","content":"The first line of input contains a single integer $k$ ($1 <= k <= 12$).The second line of input contains $3^k$ integers $a_0, \\\\dots, a_{3^k -1}$ ($0 <= a_i <= 10^3$).The third line of input contains $3^k$ integers $b_0, \\\\dots, b_{3^k -1}$ ($0 <= b_i <= 10^3$)."},{"iden":"output","content":"Output $3^k$ integers $c_0, \\\\dots, c_{3^k -1}$ separated by spaces."},{"iden":"examples","content":"Input1\n1 1 1\n1 1 1\nOutput4 3 2 \nInput2\n1 1 1 1 1 1 1 1 1\n1 1 1 1 1 1 1 1 1\nOutput16 12 8 12 9 6 8 6 4 \n"},{"iden":"note","content":"For reference: $3^(12) = 531 thin 441$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq 12 $.  \nLet $ n = 3^k $.  \nLet $ A = (a_0, a_1, \\dots, a_{n-1}) $, $ B = (b_0, b_1, \\dots, b_{n-1}) $ be sequences of non-negative integers.  \nFor $ x \\in \\{0, 1, \\dots, n-1\\} $, let $ x_i \\in \\{0,1,2\\} $ denote the $ i $-th ternary digit of $ x $, i.e., $ x = \\sum_{i=0}^{k-1} x_i \\cdot 3^i $.  \n\nDefine the tritwise mex function:  \n$$\n\\mathrm{mex}_3(i, j) = \\sum_{t=0}^{k-1} \\mathrm{mex}(i_t, j_t) \\cdot 3^t,\n$$  \nwhere $ \\mathrm{mex}(a, b) = \\min(\\{0,1,2\\} \\setminus \\{a, b\\}) $ for $ a, b \\in \\{0,1,2\\} $.  \n\n**Constraints**  \n1. $ 1 \\leq k \\leq 12 $  \n2. $ 0 \\leq a_i \\leq 10^3 $ for all $ i \\in \\{0, \\dots, n-1\\} $  \n3. $ 0 \\leq b_i \\leq 10^3 $ for all $ i \\in \\{0, \\dots, n-1\\} $  \n\n**Objective**  \nCompute the sequence $ C = (c_0, c_1, \\dots, c_{n-1}) $, where:  \n$$\nc_k = \\sum_{\\substack{0 \\leq i, j < n \\\\ \\mathrm{mex}_3(i,j) = k}} a_i \\cdot b_j\n$$","simple_statement":"Given two sequences a and b of length 3^k, compute sequence c where c[k] is the sum of a[i] * b[j] for all pairs (i,j) such that mex_3(i,j) = k.  \nmex_3(i,j) is computed digit-wise in base 3: for each digit position, take mex of the two digits (smallest non-negative integer not equal to either), then combine back into a number.","has_page_source":false}