You are given an array x2,x3,…,xn𝑥2,𝑥3,…,𝑥𝑛. Your task is to find any array a1,…,an𝑎1,…,𝑎𝑛, where:1≤ai≤1091≤𝑎𝑖≤109 for all 1≤i≤n1≤𝑖≤𝑛.xi=aimodai−1𝑥𝑖=𝑎𝑖mod𝑎𝑖−1 for all 2≤i≤n2≤𝑖≤𝑛.Here cmodd𝑐mod𝑑 denotes the remainder of the division of the integer c𝑐 by the integer d𝑑. For example 5mod2=15mod2=1, 72mod3=072mod3=0, 143mod14=3143mod14=3.Note that if there is more than one a𝑎 which satisfies the statement, you are allowed to find any.InputThe first line contains a single integer t𝑡 (1≤t≤104)(1≤𝑡≤104) — the number of test cases.The first line of each test case contains a single integer n𝑛 (2≤n≤500)(2≤𝑛≤500) — the number of elements in a𝑎.The second line of each test case contains n−1𝑛−1 integers x2,…,xn𝑥2,…,𝑥𝑛 (1≤xi≤500)(1≤𝑥𝑖≤500) — the elements of x𝑥.It is guaranteed that the sum of values n𝑛 over all test cases does not exceed 2⋅1052⋅105.OutputFor each test case output any a1,…,an𝑎1,…,𝑎𝑛 (1≤ai≤1091≤𝑎𝑖≤109) which satisfies the statement.ExampleinputCopy542 4 131 164 2 5 1 2250031 5outputCopy3 5 4 92 5 115 14 16 5 11 24501 5002 7 5NoteIn the first test case a=[3,5,4,9]𝑎=[3,5,4,9] satisfies the conditions, because:a2moda1=5mod3=2=x2𝑎2mod𝑎1=5mod3=2=𝑥2;a3moda2=4mod5=4=x3𝑎3mod𝑎2=4mod5=4=𝑥3;a4moda3=9mod4=1=x4𝑎4mod𝑎3=9mod4=1=𝑥4;

For k𝑘 positive integers x1,x2,…,xk𝑥1,𝑥2,…,𝑥𝑘, the value gcd(x1,x2,…,xk)gcd(𝑥1,𝑥2,…,𝑥𝑘) is the greatest common divisor of the integers x1,x2,…,xk𝑥1,𝑥2,…,𝑥𝑘 — the largest integer z𝑧 such that all the integers x1,x2,…,xk𝑥1,𝑥2,…,𝑥𝑘 are divisible by z𝑧.You are given three arrays a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛, b1,b2,…,bn𝑏1,𝑏2,…,𝑏𝑛 and c1,c2,…,cn𝑐1,𝑐2,…,𝑐𝑛 of length n𝑛, containing positive integers.You also have a machine that allows you to swap ai𝑎𝑖 and bi𝑏𝑖 for any i𝑖 (1≤i≤n1≤𝑖≤𝑛). Each swap costs you ci𝑐𝑖 coins.Find the maximum possible value ofgcd(a1,a2,…,an)+gcd(b1,b2,…,bn)gcd(𝑎1,𝑎2,…,𝑎𝑛)+gcd(𝑏1,𝑏2,…,𝑏𝑛)that you can get by paying in total at most d𝑑 coins for swapping some elements. The amount of coins you have changes a lot, so find the answer to this question for each of the q𝑞 possible values d1,d2,…,dq𝑑1,𝑑2,…,𝑑𝑞.InputThere are two integers on the first line — the numbers n𝑛 and q𝑞 (1≤n≤5⋅1051≤𝑛≤5⋅105, 1≤q≤5⋅1051≤𝑞≤5⋅105).On the second line, there are n𝑛 integers — the numbers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 (1≤ai≤1081≤𝑎𝑖≤108).On the third line, there are n𝑛 integers — the numbers b1,b2,…,bn𝑏1,𝑏2,…,𝑏𝑛 (1≤bi≤1081≤𝑏𝑖≤108).On the fourth line, there are n𝑛 integers — the numbers c1,c2,…,cn𝑐1,𝑐2,…,𝑐𝑛 (1≤ci≤1091≤𝑐𝑖≤109).On the fifth line, there are q𝑞 integers — the numbers d1,d2,…,dq𝑑1,𝑑2,…,𝑑𝑞 (0≤di≤10150≤𝑑𝑖≤1015).OutputPrint q𝑞 integers — the maximum value you can get for each of the q𝑞 possible values d𝑑.ExamplesinputCopy3 41 2 34 5 61 1 10 1 2 3outputCopy2 3 3 3 inputCopy5 53 4 6 8 48 3 4 9 310 20 30 40 505 55 13 1000 113outputCopy2 7 3 7 7 inputCopy1 13450outputCopy7

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.

Given an integer array and another integer element. The task is to find if the given element is present in array or not.

Given an array of length N and an integer x, you need to find if x is present in the array or not. Return true or false.Do this recursively.

You are given an array 𝐴A of size 𝑁N.Find the largest integer 𝐾K such that there exists a subsequence 𝑆S of length 𝐾K where 𝐾K is divisible by the number of distinct elements in 𝑆S.Input FormatThe first line contains a single integer 𝑇T, denoting the number of test cases.The first line of each test case contains a positive integer 𝑁N, the length of array 𝐴A.The second line contains 𝑁N space-separated integers, 𝐴1,𝐴2,…,𝐴𝑁A 1​ ,A 2​ ,…,A N​ −− denoting the array 𝐴A.Output FormatFor each test case, output the largest valid 𝐾K.Constraints1≤𝑇≤1041≤T≤10 4 1≤𝐴𝑖≤𝑁≤2⋅1051≤A i​ ≤N≤2⋅10 5 The sum of 𝑁N over all test cases won't exceed 2⋅1052⋅10 5 .Sample 1: