{"problem":{"name":"H. Hints of sd0061","description":{"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 h","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":131072},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10225H"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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.\n\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10225H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}