{"raw_statement":[{"iden":"statement","content":"_sd0061_, a legend from Beihang University ACM-ICPC Team, retired last year leaving a group of noobs with no idea how to cope with $m$ upcoming contests. What _sd0061_ left for them is only a set of hints.\n\nThere are $n$ noobs in the team, the $i$-th of which has a rating, $a_i$. _sd0061_ prepared one hint for each contest. The hint for the $j$-th contest is a number, $b_j$, which means that the noob with the $(b_j + 1)$-th lowest rating is ordained by _sd0061_ to compete in the $j$-th contest.\n\nThe coach is going to ask _constroy_ to list these contestants. Before that, _constroy_ peeked these hints and found that $b_i + b_j <= b_k$ if $b_i eq.not b_j$, $b_i < b_k$, $b_j < b_k$.\n\nNow, you are in charge of making the list for _constroy_.\n\nThe input contains multiple (about $15$) test cases.\n\nFor each test case, the first line contains five integers $n$, $m$, $A$, $B$, $C$ ($1 <= n <= 10^7$, $1 <= m <= 100$, $0 <= A, B, C < 2^(32)$).\n\nThe second line contains $m$ integers, the $i$-th number of which is $b_i$ ($0 <= b_i < n$).\n\nRatings of these $n$ noobs are obtained by calling the following C/C++ function $n$ times, the $i$-th result of which is $a_i$.\n\nIn this function, _unsigned_ means the unsigned $32$-bit integer type, and _^_ means the bitwise XOR operator. Note any integer overflow may occur in the function should be ignored, and $x$, $y$, $z$ are reset to their initial values $A$, $B$, $C$ respectively at the beginning of each test case.\n\nFor each test case, output \"_Case #x: y$\"\"_1$ y$\"\"_2$ $\\\\dots$ y$\"\"_m$_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y_i$ denotes the rating of the noob ordained for the $i$-th contest in the corresponding case.\n\n"},{"iden":"input","content":"The input contains multiple (about $15$) test cases.For each test case, the first line contains five integers $n$, $m$, $A$, $B$, $C$ ($1 <= n <= 10^7$, $1 <= m <= 100$, $0 <= A, B, C < 2^(32)$).The second line contains $m$ integers, the $i$-th number of which is $b_i$ ($0 <= b_i < n$).Ratings of these $n$ noobs are obtained by calling the following C/C++ function $n$ times, the $i$-th result of which is $a_i$.unsigned x = A, y = B, z = C;unsigned rng61() {\tunsigned t;\tx = x ^ (x << 16);\tx = x ^ (x >> 5);\tx = x ^ (x << 1);\tt = x;\tx = y;\ty = z;\tz = (t ^ x) ^ y;\treturn z;}In this function, _unsigned_ means the unsigned $32$-bit integer type, and _^_ means the bitwise XOR operator. Note any integer overflow may occur in the function should be ignored, and $x$, $y$, $z$ are reset to their initial values $A$, $B$, $C$ respectively at the beginning of each test case."},{"iden":"output","content":"For each test case, output \"_Case #x: y$\"\"_1$ y$\"\"_2$ $\\\\dots$ y$\"\"_m$_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y_i$ denotes the rating of the noob ordained for the $i$-th contest in the corresponding case."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ q \\in \\mathbb{Z} $ be the number of queries.  \nFor each $ i \\in \\{1, \\dots, q\\} $, let $ n_i, m_i \\in \\mathbb{Z} $ be integers such that $ 1 \\leq n_i < m_i \\leq 10^6 $.\n\n**Constraints**  \n1. $ 1 \\leq q \\leq 10^5 $  \n2. For each $ i $, $ 1 \\leq n_i < m_i \\leq 10^6 $\n\n**Objective**  \nFor each query $ (n_i, m_i) $, find the smallest positive integer $ x_i $ such that:  \n$$\nn_i^{x_i} \\equiv 1 \\pmod{m_i}\n$$  \nIf no such $ x_i $ exists, output $ -1 $.  \n(If multiple $ x_i $ exist, output any satisfying $ 0 \\leq x_i \\leq 10^6 $.)\n\nNote: $ x_i $ is the order of $ n_i $ modulo $ m_i $, if it exists.","simple_statement":"Find the smallest positive integer $ x $ such that $ n^x \\equiv 1 \\pmod{m} $. If no such $ x $ exists, print $-1$.","has_page_source":false}