Today, Cat and Fox found an array a𝑎 consisting of n𝑛 non-negative integers.Define the loneliness of a𝑎 as the smallest positive integer k𝑘 (1≤k≤n1≤𝑘≤𝑛) such that for any two positive integers i𝑖 and j𝑗 (1≤i,j≤n−k+11≤𝑖,𝑗≤𝑛−𝑘+1), the following holds:ai|ai+1|…|ai+k−1=aj|aj+1|…|aj+k−1,𝑎𝑖|𝑎𝑖+1|…|𝑎𝑖+𝑘−1=𝑎𝑗|𝑎𝑗+1|…|𝑎𝑗+𝑘−1,where x|y𝑥|𝑦 denotes the bitwise OR of x𝑥 and y𝑦. In other words, for every k𝑘 consecutive elements, their bitwise OR should be the same. Note that the loneliness of a𝑎 is well-defined, because for k=n𝑘=𝑛 the condition is satisfied.Cat and Fox want to know how lonely the array a𝑎 is. Help them calculate the loneliness of the found array.InputEach test consists of multiple test cases. The first line contains a single integer t𝑡 (1≤t≤1041≤𝑡≤104) — the number of test cases. The description of the test cases follows.The first line of each test case contains one integer n𝑛 (1≤n≤1051≤𝑛≤105) — the length of the array a𝑎.The second line of each test case contains n𝑛 integers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 (0≤ai<2200≤𝑎𝑖<220) — the elements of the array.It is guaranteed that the sum of n𝑛 over all test cases doesn't exceed 105105.OutputFor each test case, print one integer  — the loneliness of the given array.ExampleinputCopy71032 2 231 0 253 0 1 4 252 0 4 0 270 0 0 0 1 2 480 1 3 2 2 1 0 3outputCopy1134473

You are given a positive integer x𝑥. Find any array of integers a0,a1,…,an−1𝑎0,𝑎1,…,𝑎𝑛−1 for which the following holds:1≤n≤321≤𝑛≤32,ai𝑎𝑖 is 11, 00, or −1−1 for all 0≤i≤n−10≤𝑖≤𝑛−1,x=∑i=0n−1ai⋅2i𝑥=∑𝑖=0𝑛−1𝑎𝑖⋅2𝑖,There does not exist an index 0≤i≤n−20≤𝑖≤𝑛−2 such that both ai≠0𝑎𝑖≠0 and ai+1≠0𝑎𝑖+1≠0.It can be proven that under the constraints of the problem, a valid array always exists.InputEach test contains multiple test cases. The first line of input contains a single integer t𝑡 (1≤t≤1041≤𝑡≤104) — the number of test cases. The description of the test cases follows.The only line of each test case contains a single positive integer x𝑥 (1≤x<2301≤𝑥<230).OutputFor each test case, output two lines.On the first line, output an integer n𝑛 (1≤n≤321≤𝑛≤32) — the length of the array a0,a1,…,an−1𝑎0,𝑎1,…,𝑎𝑛−1.On the second line, output the array a0,a1,…,an−1𝑎0,𝑎1,…,𝑎𝑛−1.If there are multiple valid arrays, you can output any of them.ExampleinputCopy71142415271119outputCopy1150 -1 0 0 160 0 0 -1 0 15-1 0 0 0 16-1 0 -1 0 0 15-1 0 -1 0 15-1 0 1 0 1NoteIn the first test case, one valid array is [1][1], since (1)⋅20=1(1)⋅20=1.In the second test case, one possible valid array is [0,−1,0,0,1][0,−1,0,0,1], since (0)⋅20+(−1)⋅21+(0)⋅22+(0)⋅23+(1)⋅24=−2+16=14(0)⋅20+(−1)⋅21+(0)⋅22+(0)⋅23+(1)⋅24=−2+16=14.

Two kittens, Max and Min, play with a pair of non-negative integers x and y. As you can guess from their names, kitten Max loves to maximize and kitten Min loves to minimize. As part of this game Min wants to make sure that both numbers, x and y became negative at the same time, and kitten Max tries to prevent him from doing so.Each kitten has a set of pairs of integers available to it. Kitten Max has n pairs of non-negative integers (ai, bi) (1 ≤ i ≤ n), and kitten Min has m pairs of non-negative integers (cj, dj) (1 ≤ j ≤ m). As kitten Max makes a move, it can take any available pair (ai, bi) and add ai to x and bi to y, and kitten Min can take any available pair (cj, dj) and subtract cj from x and dj from y. Each kitten can use each pair multiple times during distinct moves.Max moves first. Kitten Min is winning if at some moment both numbers a, b are negative simultaneously. Otherwise, the winner of the game is kitten Max. Determine which kitten wins if both of them play optimally.InputThe first line contains two integers, n and m (1 ≤ n, m ≤ 100 000) — the number of pairs of numbers available to Max and Min, correspondingly.The second line contains two integers x, y (1 ≤ x, y ≤ 109) — the initial values of numbers with which the kittens are playing.Next n lines contain the pairs of numbers ai, bi (1 ≤ ai, bi ≤ 109) — the pairs available to Max.The last m lines contain pairs of numbers cj, dj (1 ≤ cj, dj ≤ 109) — the pairs available to Min.OutputPrint «Max» (without the quotes), if kitten Max wins, or "Min" (without the quotes), if kitten Min wins.

Make My Array EqualYou are given an array 𝐴A of length 𝑁N.Determine if it is possible to make all the elements of 𝐴A equal by performing the following operation any number of times (possibly, zero):Choose two distinct indices 𝑖i and 𝑗j (1≤𝑖,𝑗≤𝑁1≤i,j≤N, 𝑖≠𝑗i=j); andUpdate the value at index 𝑖i by setting 𝐴𝑖A i​ to 𝐴𝑖+𝐴𝑗A i​ +A j​ .For example, if 𝐴=[1,5,3,5,6]A=[1,5,3,5,6],Choosing 𝑖=5i=5 and 𝑗=3j=3 would result in the array [1,5,3,5,9][1,5,3,5,9], since we replace 𝐴5A 5​ with 𝐴5+𝐴3=9A 5​ +A 3​ =9.Choosing 𝑖=2i=2 and 𝑗=4j=4 would instead result in the array [1,10,3,5,6][1,10,3,5,6].Output "YES" if it is possible to make all elements of the array equal after performing several (possibly, zero) of these operations, otherwise output "NO" (without quotes).Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of two lines of input.The first line of each test case contains a single integer 𝑁N — the length of array.The second line of each test case contains 𝑁N space-separated integers 𝐴1,𝐴2,…,𝐴𝑁A 1​ ,A 2​ ,…,A N​ , denoting the initial array.Output FormatFor each test case, print Yes if it is possible to make all elements of array equal using any number of operations, otherwise print No.You may print each character of the output in either uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).Constraints1≤𝑇≤1051≤T≤10 5 1≤𝑁≤2⋅1051≤N≤2⋅10 5 0≤𝐴𝑖≤1090≤A i​ ≤10 9 The sum of 𝑁N over all test cases won't exceed 2⋅1052⋅10 5 .Sample 1:InputOutput331 1 121 231 0 0YESNOYES

Make PermutationChef has an array 𝐴A of size 𝑁N. He wants to make a permutation†† using this array.Find whether there exists an array 𝐵B consisting of 𝑁N non-negative integers, such that the array 𝐶C constructed as 𝐶𝑖=𝐴𝑖+𝐵𝑖C i​ =A i​ +B i​ is a permutation.†† A permutation of size 𝑁N is an array of 𝑁N distinct elements in the range [1,𝑁][1,N]. For example, [4,2,1,3][4,2,1,3] is a permutation of size 44, while [3,2,2,1][3,2,2,1] and [1,3,4][1,3,4] are not.Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of multiple lines of input.The first line of each test case consists of 𝑁N - the size of the array 𝐴AThe next line contains 𝑁N space-separated integers - 𝐴1,𝐴2,…,𝐴𝑁A 1​ ,A 2​ ,…,A N​ - the elements of array 𝐴A.Output FormatFor each test case, output YES if there exists an array 𝐵B such that array 𝐶C constructed as 𝐶𝑖=𝐴𝑖+𝐵𝑖C i​ =A i​ +B i​ is a permutation, otherwise output NO.You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).Constraints1≤𝑇≤1001≤T≤1001≤𝑁≤1001≤N≤1001≤𝐴𝑖≤𝑁1≤A i​ ≤NSample 1:InputOutput454 1 3 2 152 4 3 4 21161 1 1 1 6 6YESNOYESNOExplanation:Test case 11 : Consider 𝐵=[0,4,0,0,0]B=[0,4,0,0,0]. The corresponding array 𝐶C becomes [4,5,3,2,1][4,5,3,2,1], which is a permutation. Some other possible values of 𝐵B for which 𝐶C is a permutation are [1,0,1,1,1][1,0,1,1,1] and [1,3,0,0,0][1,3,0,0,0].Test case 22 : It can be proven that no valid array 𝐵B exists.

Let lowbit(x)lowbit⁡(𝑥) denote the value of the lowest binary bit of x𝑥, e.g. lowbit(12)=4lowbit⁡(12)=4, lowbit(8)=8lowbit⁡(8)=8.For an array a𝑎 of length n𝑛, if an array s𝑠 of length n𝑛 satisfies sk=(∑i=k−lowbit(k)+1kai)mod998244353𝑠𝑘=(∑𝑖=𝑘−lowbit⁡(𝑘)+1𝑘𝑎𝑖)mod998244353 for all k𝑘, then s𝑠 is called the Fenwick Tree of a𝑎. Let's denote it as s=f(a)𝑠=𝑓(𝑎).For a positive integer k𝑘 and an array a𝑎, fk(a)𝑓𝑘(𝑎) is defined as follows:fk(a)={f(a)f(fk−1(a))if k=1otherwise.𝑓𝑘(𝑎)={𝑓(𝑎)if 𝑘=1𝑓(𝑓𝑘−1(𝑎))otherwise.You are given an array b𝑏 of length n𝑛 and a positive integer k𝑘. Find an array a𝑎 that satisfies 0≤ai<9982443530≤𝑎𝑖<998244353 and fk(a)=b𝑓𝑘(𝑎)=𝑏. It can be proved that an answer always exists. If there are multiple possible answers, you may print any of them.InputEach test contains multiple test cases. The first line contains the number of test cases t𝑡 (1≤t≤1041≤𝑡≤104). The description of the test cases follows.The first line of each test case contains two positive integers n𝑛 (1≤n≤2⋅1051≤𝑛≤2⋅105) and k𝑘 (1≤k≤1091≤𝑘≤109), representing the length of the array and the number of times the function f𝑓 is performed.The second line of each test case contains an array b𝑏 of length n𝑛 (0≤bi<9982443530≤𝑏𝑖<998244353).It is guaranteed that the sum of n𝑛 over all test cases does not exceed 2⋅1052⋅105.OutputFor each test case, print a single line, containing a valid array a𝑎 of length n𝑛.ExampleinputCopy28 11 2 1 4 1 2 1 86 21 4 3 17 5 16outputCopy1 1 1 1 1 1 1 11 2 3 4 5 6