{"problem":{"name":"C. Jon Snow and his Favourite Number","description":{"content":"Jon Snow now has to fight with White Walkers. He has _n_ rangers, each of which has his own strength. Also Jon Snow has his favourite number _x_. Each ranger can fight with a white walker only if the ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF768C"},"statements":[{"statement_type":"Markdown","content":"Jon Snow now has to fight with White Walkers. He has _n_ rangers, each of which has his own strength. Also Jon Snow has his favourite number _x_. Each ranger can fight with a white walker only if the strength of the white walker equals his strength. He however thinks that his rangers are weak and need to improve. Jon now thinks that if he takes the bitwise XOR of strengths of some of rangers with his favourite number _x_, he might get soldiers of high strength. So, he decided to do the following operation _k_ times:\n\n1.  Arrange all the rangers in a straight line in the order of increasing strengths.\n2.  Take the bitwise XOR (is written as ) of the strength of each alternate ranger with _x_ and update it's strength.\n\nSuppose, Jon has 5 rangers with strengths \\[9, 7, 11, 15, 5\\] and he performs the operation 1 time with _x_ = 2. He first arranges them in the order of their strengths, \\[5, 7, 9, 11, 15\\]. Then he does the following:\n\n1.  The strength of first ranger is updated to , i.e. 7.\n2.  The strength of second ranger remains the same, i.e. 7.\n3.  The strength of third ranger is updated to , i.e. 11.\n4.  The strength of fourth ranger remains the same, i.e. 11.\n5.  The strength of fifth ranger is updated to , i.e. 13.\n\nThe new strengths of the 5 rangers are \\[7, 7, 11, 11, 13\\]Now, Jon wants to know the maximum and minimum strength of the rangers after performing the above operations _k_ times. He wants your help for this task. Can you help him?\n\n## Input\n\nFirst line consists of three integers _n_, _k_, _x_ (1 ≤ _n_ ≤ 105, 0 ≤ _k_ ≤ 105, 0 ≤ _x_ ≤ 103) — number of rangers Jon has, the number of times Jon will carry out the operation and Jon's favourite number respectively.\n\nSecond line consists of _n_ integers representing the strengths of the rangers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 103).\n\n## Output\n\nOutput two integers, the maximum and the minimum strength of the rangers after performing the operation _k_ times.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"琼恩·雪诺现在需要与白 walkers 作战。他有 #cf_span[n] 名游骑兵，每人拥有自己的力量值。此外，琼恩·雪诺有一个他最喜欢数字 #cf_span[x]。每个游骑兵只能在白 walker 的力量值等于他自身力量值时与之战斗。然而，他认为他的游骑兵太弱，需要提升。琼恩现在认为，如果他将某些游骑兵的力量值与他最喜欢数字 #cf_span[x] 进行按位异或运算，他可能会获得力量更强的士兵。因此，他决定执行以下操作 #cf_span[k] 次：\n\n现在，琼恩想知道在执行上述操作 #cf_span[k] 次后，游骑兵的最大和最小力量值是多少。他需要你的帮助来完成这个任务。你能帮他吗？\n\n第一行包含三个整数 #cf_span[n], #cf_span[k], #cf_span[x]（#cf_span[1 ≤ n ≤ 105], #cf_span[0 ≤ k ≤ 105], #cf_span[0 ≤ x ≤ 103]）——分别表示琼恩拥有的游骑兵数量、执行操作的次数以及琼恩最喜欢数字。\n\n第二行包含 #cf_span[n] 个整数，表示游骑兵的力量值 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 103]）。\n\n请输出两个整数，分别表示执行 #cf_span[k] 次操作后游骑兵的最大和最小力量值。\n\n## Input\n\n第一行包含三个整数 #cf_span[n], #cf_span[k], #cf_span[x]（#cf_span[1 ≤ n ≤ 105], #cf_span[0 ≤ k ≤ 105], #cf_span[0 ≤ x ≤ 103]）——分别表示琼恩拥有的游骑兵数量、执行操作的次数以及琼恩最喜欢数字。第二行包含 #cf_span[n] 个整数，表示游骑兵的力量值 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 103]）。\n\n## Output\n\n请输出两个整数，分别表示执行 #cf_span[k] 次操作后游骑兵的最大和最小力量值。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k, x \\in \\mathbb{Z} $ be given integers.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in [0, 1000] $.  \nLet $ \\oplus $ denote the bitwise XOR operation.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 0 \\leq k \\leq 10^5 $  \n3. $ 0 \\leq x \\leq 1000 $  \n4. $ 0 \\leq a_i \\leq 1000 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Operation**  \nIn each operation, exactly one ranger’s strength $ a_i $ is replaced by $ a_i \\oplus x $.  \nThis operation is performed exactly $ k $ times (each time applied to *one* ranger, chosen arbitrarily).\n\n**Objective**  \nAfter $ k $ operations, determine:  \n- $ \\max_{\\text{final}} = \\max \\{ \\text{possible values of } \\max(A') \\} $  \n- $ \\min_{\\text{final}} = \\min \\{ \\text{possible values of } \\min(A') \\} $  \n\nwhere $ A' $ is the sequence obtained after $ k $ operations.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF768C","tags":["brute force","dp","implementation","sortings"],"sample_group":[["5 1 2\n9 7 11 15 5","13 7"],["2 100000 569\n605 986","986 605"]],"created_at":"2026-03-03 11:00:39"}}