{"raw_statement":[{"iden":"problem statement","content":"You are given two sequences of non-negative integers $A$ and $B$, each of length $N$. Initially, $A=(A_1, A_2, \\ldots, A_N)$ and $B=(B_1, B_2, \\ldots, B_N)$.\nYou will be given $Q$ queries. Process them in the order they are given.\nEach query is one of the following two types:\n\n*   Type $1$: Given in the format `1 i a b`. Update the value of $A_i$ to $a$ and the value of $B_i$ to $b$.\n*   Type $2$: Given in the format `2 Y 0 0`. Solve the following problem:\n    \n    > For a non-negative integer $S$, define a sequence of non-negative integers $X = (X_0, X_1, \\dots, X_N)$ using the following recurrence:\n    > \n    > *   $X_0 = S$\n    > *   For each $1 \\le i \\le N$, $X_i = \\begin{cases} X_{i - 1} \\oplus A_i & \\text{if } X_{i - 1} \\equiv 1 \\pmod{2} \\\\ X_{i - 1} \\oplus B_i & \\text{if } X_{i - 1} \\equiv 0 \\pmod{2} \\end{cases}$\n    > \n    > Determine whether it is possible to set a non-negative integer $S$ such that $X_N = Y$. If possible, output the smallest such $S$.  \n    > If no such $S$ exists, output `-1`."},{"iden":"constraints","content":"*   All inputs are integers.\n*   $1 \\le N \\le 2 \\times 10^5$\n*   $1 \\le Q \\le 2 \\times 10^5$\n*   $0 \\le A_i, B_i < 2^{60} \\ (1 \\le i \\le N)$\n*   For a Type $1$ query, $1 \\le i \\le N$, $0 \\le a, b < 2^{60}$\n*   For a Type $2$ query, $0 \\le Y < 2^{60}$\n*   There is at least one Type $2$ query."},{"iden":"partial score","content":"$30$ points will be awarded for passing the test set satisfying the additional constraint $Q=1$."},{"iden":"input","content":"The input is given in the following format:\n\n$N$ $Q$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n$B_1$ $B_2$ $\\ldots$ $B_N$\n$\\mathrm{query}_1$\n$\\vdots$\n$\\mathrm{query}_Q$\n\nHere, $\\mathrm{query}_i$ represents the $i$\\-th query and is given in one of the following formats:\n\n1 $i$ $a$ $b$\n\n2 $Y$ 0 0"},{"iden":"sample input 1","content":"1 3\n0\n1\n2 5 0 0\n2 6 0 0\n2 7 0 0"},{"iden":"sample output 1","content":"4\n-1\n6\n\nGiven $A = (0),\\ B = (1)$, the value of $X_N$ is:\n\n*   $X_N = S$ if $S$ is odd.\n*   $X_N = S \\oplus 1$ if $S$ is even.\n\nFor the first query with $Y = 5$, both $S = 4$ and $S = 5$ result in $X_N = 5$, so the smallest $S$ is $4$.  \nFor the second query with $Y = 6$, there is no $S$ such that $X_N = 6$, so output `-1`.  \nFor the third query with $Y = 7$, both $S = 6$ and $S = 7$ result in $X_N = 7$, so the smallest $S$ is $6$."},{"iden":"sample input 2","content":"10 1\n310214852498133736 505276263682091678 273987911350501637 317207700241861186 878845869214220663 722059890180131902 597424946894933345 74297940232615233 969543184238991085 567669635596262039\n760374976835769237 114205047640377864 975115657391620675 659404150340533368 514313531921108960 255579815636209538 1042405225853490071 891193105039531117 1032475514675208675 968262176137127595\n2 942999108116930288 0 0"},{"iden":"sample output 2","content":"494185924924343867"},{"iden":"sample input 3","content":"10 5\n20 19 18 17 16 15 14 13 12 11\n11 12 13 14 15 16 17 18 19 20\n2 8 0 0\n1 6 100 200\n2 12 0 0\n1 10 32 662\n2 100 0 0"},{"iden":"sample output 3","content":"8\n103\n-1"},{"iden":"sample input 4","content":"10 5\n464468010685205695 652469322679259637 207750579744900414 551282264132274959 477385551779769369 457669217633528368 1124978699497706079 993018743713584412 347799342391956023 253839229959865684\n43481420251962425 913779804742334221 721829783836314668 643562100144275666 148532568860178532 348780722732705987 905040003050597634 962374691997649953 160408954061784257 6313574278114070\n2 942999108116930288 0 0\n1 7 911289147093700219 315969390490734880\n2 570806468566359262 0 0\n1 5 865153057674787555 127079554510737035\n2 71991180131886804 0 0"},{"iden":"sample output 4","content":"167766290121628811\n833427363106128513\n657636533261400102"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}