[Solution] Prove Him Wrong solution codeforces

Prove Him Wrong solution codeforces – Recently, your friend discovered one special operation on an integer array 𝑎a:

  1. Choose two indices 𝑖i and 𝑗j (𝑖𝑗i≠j);
  2. Set 𝑎𝑖=𝑎𝑗=|𝑎𝑖𝑎𝑗|ai=aj=|ai−aj|.

After playing with this operation for a while, he came to the next conclusion:

  • For every array 𝑎a of 𝑛n integers, where 1𝑎𝑖1091≤ai≤109, you can find a pair of indices (𝑖,𝑗)(i,j) such that the total sum of 𝑎a will decrease after performing the operation.

Prove Him Wrong solution codeforces

This statement sounds fishy to you, so you want to find a counterexample for a given integer 𝑛n. Can you find such counterexample and prove him wrong?

In other words, find an array 𝑎a consisting of 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) such that for all pairs of indices (𝑖,𝑗)(i,j) performing the operation won’t decrease the total sum (it will increase or not change the sum).

Input

The first line contains a single integer 𝑡t (1𝑡1001≤t≤100) — the number of test cases. Then 𝑡t test cases follow.

The first and only line of each test case contains a single integer 𝑛n (2𝑛10002≤n≤1000) — the length of array 𝑎a.

Prove Him Wrong solution codeforces

For each test case, if there is no counterexample array 𝑎a of size 𝑛n, print NO.

Otherwise, print YES followed by the array 𝑎a itself (1𝑎𝑖1091≤ai≤109). If there are multiple counterexamples, print any.

Example
input

Copy
3
2
512
3
output

Copy
YES
1 337
NO
YES
31 4 159

Prove Him Wrong solution codeforces

In the first test case, the only possible pairs of indices are (1,2)(1,2) and (2,1)(2,1).

If you perform the operation on indices (1,2)(1,2) (or (2,1)(2,1)), you’ll get 𝑎1=𝑎2=|1337|=336a1=a2=|1−337|=336, or array [336,336][336,336]. In both cases, the total sum increases, so this array 𝑎a is a counterexample.

Leave a Comment