meetforever/GRPO_CL huggingface dataset:
user: You are playing a variation of game 2048. Initially you have a multiset $s$ of $n$ integers. Every integer in this multiset is a power of two. 

You may perform any number (possibly, zero) operations with this multiset.

During each operation you choose two equal integers from $s$, remove them from $s$ and insert the number equal to their sum into $s$.

For example, if $s = \{1, 2, 1, 1, 4, 2, 2\}$ and you choose integers $2$ and $2$, then the multiset becomes $\{1, 1, 1, 4, 4, 2\}$.

You win if the number $2048$ belongs to your multiset. For example, if $s = \{1024, 512, 512, 4\}$ you can win as follows: choose $512$ and $512$, your multiset turns into $\{1024, 1024, 4\}$. Then choose $1024$ and $1024$, your multiset turns into $\{2048, 4\}$ and you win.

You have to determine if you can win this game.

You have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 100$) – the number of queries.

The first line of each query contains one integer $n$ ($1 \le n \le 100$) — the number of elements in multiset.

The second line of each query contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \le s_i \le 2^{29}$) — the description of the multiset. It is guaranteed that all elements of the multiset are powers of two. 


-----Output-----

For each query print YES if it is possible to obtain the number $2048$ in your multiset, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).


-----Example-----
Input
6
4
1024 512 64 512
1
2048
3
64 512 2
2
4096 4
7
2048 2 2048 2048 2048 2048 2048
2
2048 4096

Output
YES
YES
NO
NO
YES
YES



-----Note-----

In the first query you can win as follows: choose $512$ and $512$, and $s$ turns into $\{1024, 64, 1024\}$. Then choose $1024$ and $1024$, and $s$ turns into $\{2048, 64\}$ and you win.

In the second query $s$ contains $2048$ initially.
user: A penguin Rocher has $n$ sticks. He has exactly one stick with length $i$ for all $1 \le i \le n$.

He can connect some sticks. If he connects two sticks that have lengths $a$ and $b$, he gets one stick with length $a + b$. Two sticks, that were used in the operation disappear from his set and the new connected stick appears in his set and can be used for the next connections.

He wants to create the maximum number of sticks that have the same length. It is not necessary to make all sticks have the same length, some sticks can have the other length. How many sticks with the equal length he can create?


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

For each test case, the only line contains a single integer $n$ ($1 \le n \le 10^{9}$).


-----Output-----

For each test case, print a single integer  — the answer to the problem.


-----Example-----
Input
4
1
2
3
4

Output
1
1
2
2



-----Note-----

In the third case, he can connect two sticks with lengths $1$ and $2$ and he will get one stick with length $3$. So, he will have two sticks with lengths $3$.

In the fourth case, he can connect two sticks with lengths $1$ and $3$ and he will get one stick with length $4$. After that, he will have three sticks with lengths $\{2, 4, 4\}$, so two sticks have the same length, and one stick has the other length.
user: A mad scientist Dr.Jubal has made a competitive programming task. Try to solve it!

You are given integers $n,k$. Construct a grid $A$ with size $n \times n$ consisting of integers $0$ and $1$. The very important condition should be satisfied: the sum of all elements in the grid is exactly $k$. In other words, the number of $1$ in the grid is equal to $k$.

Let's define:  $A_{i,j}$ as the integer in the $i$-th row and the $j$-th column.  $R_i = A_{i,1}+A_{i,2}+...+A_{i,n}$ (for all $1 \le i \le n$).  $C_j = A_{1,j}+A_{2,j}+...+A_{n,j}$ (for all $1 \le j \le n$).  In other words, $R_i$ are row sums and $C_j$ are column sums of the grid $A$.  For the grid $A$ let's define the value $f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2$ (here for an integer sequence $X$ we define $\max(X)$ as the maximum value in $X$ and $\min(X)$ as the minimum value in $X$). 

Find any grid $A$, which satisfies the following condition. Among such grids find any, for which the value $f(A)$ is the minimum possible. Among such tables, you can find any.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

For each test case the only line contains two integers $n$, $k$ $(1 \le n \le 300, 0 \le k \le n^2)$.

It is guaranteed that the sum of $n^2$ for all test cases does not exceed $10^5$.


-----Output-----

For each test case, firstly print the minimum possible value of $f(A)$ among all tables, for which the condition is satisfied.

After that, print $n$ lines contain $n$ characters each. The $j$-th character in the $i$-th line should be equal to $A_{i,j}$.

If there are multiple answers you can print any.


-----Example-----
Input
4
2 2
3 8
1 0
4 16

Output
0
10
01
2
111
111
101
0
0
0
1111
1111
1111
1111



-----Note-----

In the first test case, the sum of all elements in the grid is equal to $2$, so the condition is satisfied. $R_1 = 1, R_2 = 1$ and $C_1 = 1, C_2 = 1$. Then, $f(A) = (1-1)^2 + (1-1)^2 = 0$, which is the minimum possible value of $f(A)$.

In the second test case, the sum of all elements in the grid is equal to $8$, so the condition is satisfied. $R_1 = 3, R_2 = 3, R_3 = 2$ and $C_1 = 3, C_2 = 2, C_3 = 3$. Then, $f(A) = (3-2)^2 + (3-2)^2 = 2$. It can be proven, that it is the minimum possible value of $f(A)$.
user: You are given an array $a$ of length $n$, which initially is a permutation of numbers from $1$ to $n$. In one operation, you can choose an index $i$ ($1 \leq i < n$) such that $a_i < a_{i + 1}$, and remove either $a_i$ or $a_{i + 1}$ from the array (after the removal, the remaining parts are concatenated). 

For example, if you have the array $[1, 3, 2]$, you can choose $i = 1$ (since $a_1 = 1 < a_2 = 3$), then either remove $a_1$ which gives the new array $[3, 2]$, or remove $a_2$ which gives the new array $[1, 2]$.

Is it possible to make the length of this array equal to $1$ with these operations?


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^4$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 3 \cdot 10^5$)  — the length of the array.

The second line of each test case contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \leq a_i \leq n$, $a_i$ are pairwise distinct) — elements of the array.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.


-----Output-----

For each test case, output on a single line the word "YES" if it is possible to reduce the array to a single element using the aforementioned operation, or "NO" if it is impossible to do so.


-----Example-----
Input
4
3
1 2 3
4
3 1 2 4
3
2 3 1
6
2 4 6 1 3 5

Output
YES
YES
NO
YES



-----Note-----

For the first two test cases and the fourth test case, we can operate as follow (the bolded elements are the pair chosen for that operation):

$[\text{1}, \textbf{2}, \textbf{3}] \rightarrow [\textbf{1}, \textbf{2}] \rightarrow [\text{1}]$

$[\text{3}, \textbf{1}, \textbf{2}, \text{4}] \rightarrow [\text{3}, \textbf{1}, \textbf{4}] \rightarrow [\textbf{3}, \textbf{4}] \rightarrow [\text{4}]$

$[\textbf{2}, \textbf{4}, \text{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\textbf{4}, \textbf{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\text{4}, \text{1}, \textbf{3}, \textbf{5}] \rightarrow [\text{4}, \textbf{1}, \textbf{5}] \rightarrow [\textbf{4}, \textbf{5}] \rightarrow [\text{4}]$
user: You have a rectangular chocolate bar consisting of n × m single squares. You want to eat exactly k squares, so you may need to break the chocolate bar. 

In one move you can break any single rectangular piece of chocolate in two rectangular pieces. You can break only by lines between squares: horizontally or vertically. The cost of breaking is equal to square of the break length.

For example, if you have a chocolate bar consisting of 2 × 3 unit squares then you can break it horizontally and get two 1 × 3 pieces (the cost of such breaking is 3^2 = 9), or you can break it vertically in two ways and get two pieces: 2 × 1 and 2 × 2 (the cost of such breaking is 2^2 = 4).

For several given values n, m and k find the minimum total cost of breaking. You can eat exactly k squares of chocolate if after all operations of breaking there is a set of rectangular pieces of chocolate with the total size equal to k squares. The remaining n·m - k squares are not necessarily form a single rectangular piece.


-----Input-----

The first line of the input contains a single integer t (1 ≤ t ≤ 40910) — the number of values n, m and k to process.

Each of the next t lines contains three integers n, m and k (1 ≤ n, m ≤ 30, 1 ≤ k ≤ min(n·m, 50)) — the dimensions of the chocolate bar and the number of squares you want to eat respectively.


-----Output-----

For each n, m and k print the minimum total cost needed to break the chocolate bar, in order to make it possible to eat exactly k squares.


-----Examples-----
Input
4
2 2 1
2 2 3
2 2 2
2 2 4

Output
5
5
4
0



-----Note-----

In the first query of the sample one needs to perform two breaks:  to split 2 × 2 bar into two pieces of 2 × 1 (cost is 2^2 = 4),  to split the resulting 2 × 1 into two 1 × 1 pieces (cost is 1^2 = 1). 

In the second query of the sample one wants to eat 3 unit squares. One can use exactly the same strategy as in the first query of the sample.
user: Dark is going to attend Motarack's birthday. Dark decided that the gift he is going to give to Motarack is an array $a$ of $n$ non-negative integers.

Dark created that array $1000$ years ago, so some elements in that array disappeared. Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them. He doesn't have much time so he wants to choose an integer $k$ ($0 \leq k \leq 10^{9}$) and replaces all missing elements in the array $a$ with $k$.

Let $m$ be the maximum absolute difference between all adjacent elements (i.e. the maximum value of $|a_i - a_{i+1}|$ for all $1 \leq i \leq n - 1$) in the array $a$ after Dark replaces all missing elements with $k$.

Dark should choose an integer $k$ so that $m$ is minimized. Can you help him?


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^{5}$) — the size of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-1 \leq a_i \leq 10 ^ {9}$). If $a_i = -1$, then the $i$-th integer is missing. It is guaranteed that at least one integer is missing in every test case.

It is guaranteed, that the sum of $n$ for all test cases does not exceed $4 \cdot 10 ^ {5}$.


-----Output-----

Print the answers for each test case in the following format:

You should print two integers, the minimum possible value of $m$ and an integer $k$ ($0 \leq k \leq 10^{9}$) that makes the maximum absolute difference between adjacent elements in the array $a$ equal to $m$.

Make sure that after replacing all the missing elements with $k$, the maximum absolute difference between adjacent elements becomes $m$.

If there is more than one possible $k$, you can print any of them.


-----Example-----
Input
7
5
-1 10 -1 12 -1
5
-1 40 35 -1 35
6
-1 -1 9 -1 3 -1
2
-1 -1
2
0 -1
4
1 -1 3 -1
7
1 -1 7 5 2 -1 5

Output
1 11
5 35
3 6
0 42
0 0
1 2
3 4



-----Note-----

In the first test case after replacing all missing elements with $11$ the array becomes $[11, 10, 11, 12, 11]$. The absolute difference between any adjacent elements is $1$. It is impossible to choose a value of $k$, such that the absolute difference between any adjacent element will be $\leq 0$. So, the answer is $1$.

In the third test case after replacing all missing elements with $6$ the array becomes $[6, 6, 9, 6, 3, 6]$.  $|a_1 - a_2| = |6 - 6| = 0$;  $|a_2 - a_3| = |6 - 9| = 3$;  $|a_3 - a_4| = |9 - 6| = 3$;  $|a_4 - a_5| = |6 - 3| = 3$;  $|a_5 - a_6| = |3 - 6| = 3$. 

So, the maximum difference between any adjacent elements is $3$.
user: In order to celebrate Twice's 5th anniversary, Tzuyu and Sana decided to play a game.

Tzuyu gave Sana two integers $a$ and $b$ and a really important quest.

In order to complete the quest, Sana has to output the smallest possible value of ($a \oplus x$) + ($b \oplus x$) for any given $x$, where $\oplus$ denotes the bitwise XOR operation. 


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^{4}$). Description of the test cases follows.

The only line of each test case contains two integers $a$ and $b$ ($1 \le a, b \le 10^{9}$).


-----Output-----

For each testcase, output the smallest possible value of the given expression.


-----Example-----
Input
6
6 12
4 9
59 832
28 14
4925 2912
1 1

Output
10
13
891
18
6237
0



-----Note-----

For the first test case Sana can choose $x=4$ and the value will be ($6 \oplus 4$) + ($12 \oplus 4$) = $2 + 8$ = $10$. It can be shown that this is the smallest possible value.
user: You are given a permutation $p_1, p_2, \dots, p_n$. Recall that sequence of $n$ integers is called a permutation if it contains all integers from $1$ to $n$ exactly once.

Find three indices $i$, $j$ and $k$ such that:   $1 \le i < j < k \le n$;  $p_i < p_j$ and $p_j > p_k$.  Or say that there are no such indices.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 200$) — the number of test cases.

Next $2T$ lines contain test cases — two lines per test case. The first line of each test case contains the single integer $n$ ($3 \le n \le 1000$) — the length of the permutation $p$.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$; $p_i \neq p_j$ if $i \neq j$) — the permutation $p$.


-----Output-----

For each test case:   if there are such indices $i$, $j$ and $k$, print YES (case insensitive) and the indices themselves;  if there are no such indices, print NO (case insensitive). 

If there are multiple valid triples of indices, print any of them.


-----Example-----
Input
3
4
2 1 4 3
6
4 6 1 2 5 3
5
5 3 1 2 4

Output
YES
2 3 4
YES
3 5 6
NO
user: Polycarp wants to assemble his own keyboard. Layouts with multiple rows are too complicated for him — his keyboard will consist of only one row, where all $26$ lowercase Latin letters will be arranged in some order.

Polycarp uses the same password $s$ on all websites where he is registered (it is bad, but he doesn't care). He wants to assemble a keyboard that will allow to type this password very easily. He doesn't like to move his fingers while typing the password, so, for each pair of adjacent characters in $s$, they should be adjacent on the keyboard. For example, if the password is abacaba, then the layout cabdefghi... is perfect, since characters a and c are adjacent on the keyboard, and a and b are adjacent on the keyboard. It is guaranteed that there are no two adjacent equal characters in $s$, so, for example, the password cannot be password (two characters s are adjacent).

Can you help Polycarp with choosing the perfect layout of the keyboard, if it is possible?


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 1000$) — the number of test cases.

Then $T$ lines follow, each containing one string $s$ ($1 \le |s| \le 200$) representing the test case. $s$ consists of lowercase Latin letters only. There are no two adjacent equal characters in $s$.


-----Output-----

For each test case, do the following:

  if it is impossible to assemble a perfect keyboard, print NO (in upper case, it matters in this problem);  otherwise, print YES (in upper case), and then a string consisting of $26$ lowercase Latin letters — the perfect layout. Each Latin letter should appear in this string exactly once. If there are multiple answers, print any of them. 


-----Example-----
Input
5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza

Output
YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO
user: Lee just became Master in Codeforces, and so, he went out to buy some gifts for his friends. He bought $n$ integers, now it's time to distribute them between his friends rationally...

Lee has $n$ integers $a_1, a_2, \ldots, a_n$ in his backpack and he has $k$ friends. Lee would like to distribute all integers in his backpack between his friends, such that the $i$-th friend will get exactly $w_i$ integers and each integer will be handed over to exactly one friend.

Let's define the happiness of a friend as the sum of the maximum and the minimum integer he'll get.

Lee would like to make his friends as happy as possible, in other words, he'd like to maximize the sum of friends' happiness. Now he asks you to calculate the maximum sum of friends' happiness.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Next $3t$ lines contain test cases — one per three lines.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le n$) — the number of integers Lee has and the number of Lee's friends.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the integers Lee has.

The third line contains $k$ integers $w_1, w_2, \ldots, w_k$ ($1 \le w_i \le n$; $w_1 + w_2 + \ldots + w_k = n$) — the number of integers Lee wants to give to each friend. 

It's guaranteed that the sum of $n$ over test cases is less than or equal to $2 \cdot 10^5$.


-----Output-----

For each test case, print a single integer — the maximum sum of happiness Lee can achieve.


-----Example-----
Input
3
4 2
1 13 7 17
1 3
6 2
10 10 10 10 11 11
3 3
4 4
1000000000 1000000000 1000000000 1000000000
1 1 1 1

Output
48
42
8000000000



-----Note-----

In the first test case, Lee should give the greatest integer to the first friend (his happiness will be $17 + 17$) and remaining integers to the second friend (his happiness will be $13 + 1$).

In the second test case, Lee should give $\{10, 10, 11\}$ to the first friend and to the second friend, so the total happiness will be equal to $(11 + 10) + (11 + 10)$

In the third test case, Lee has four friends and four integers, it doesn't matter how he distributes the integers between his friends.
user: There is a road with length $l$ meters. The start of the road has coordinate $0$, the end of the road has coordinate $l$.

There are two cars, the first standing at the start of the road and the second standing at the end of the road. They will start driving simultaneously. The first car will drive from the start to the end and the second car will drive from the end to the start.

Initially, they will drive with a speed of $1$ meter per second. There are $n$ flags at different coordinates $a_1, a_2, \ldots, a_n$. Each time when any of two cars drives through a flag, the speed of that car increases by $1$ meter per second.

Find how long will it take for cars to meet (to reach the same coordinate). 


-----Input-----

The first line contains one integer $t$ ($1 \leq t \leq 10^4$): the number of test cases.

The first line of each test case contains two integers $n$, $l$ ($1 \leq n \leq 10^5$, $1 \leq l \leq 10^9$): the number of flags and the length of the road.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ in the increasing order ($1 \leq a_1 < a_2 < \ldots < a_n < l$).

It is guaranteed that the sum of $n$ among all test cases does not exceed $10^5$.


-----Output-----

For each test case print a single real number: the time required for cars to meet.

Your answer will be considered correct, if its absolute or relative error does not exceed $10^{-6}$. More formally, if your answer is $a$ and jury's answer is $b$, your answer will be considered correct if $\frac{|a-b|}{\max{(1, b)}} \leq 10^{-6}$.


-----Example-----
Input
5
2 10
1 9
1 10
1
5 7
1 2 3 4 6
2 1000000000
413470354 982876160
9 478
1 10 25 33 239 445 453 468 477

Output
3.000000000000000
3.666666666666667
2.047619047619048
329737645.750000000000000
53.700000000000000



-----Note-----

In the first test case cars will meet in the coordinate $5$.

The first car will be in the coordinate $1$ in $1$ second and after that its speed will increase by $1$ and will be equal to $2$ meters per second. After $2$ more seconds it will be in the coordinate $5$. So, it will be in the coordinate $5$ in $3$ seconds.

The second car will be in the coordinate $9$ in $1$ second and after that its speed will increase by $1$ and will be equal to $2$ meters per second. After $2$ more seconds it will be in the coordinate $5$. So, it will be in the coordinate $5$ in $3$ seconds.

In the second test case after $1$ second the first car will be in the coordinate $1$ and will have the speed equal to $2$ meters per second, the second car will be in the coordinate $9$ and will have the speed equal to $1$ meter per second. So, they will meet after $\frac{9-1}{2+1} = \frac{8}{3}$ seconds. So, the answer is equal to $1 + \frac{8}{3} = \frac{11}{3}$.
user: You and your friend are playing the game Mortal Kombat XI. You are trying to pass a challenge tower. There are $n$ bosses in this tower, numbered from $1$ to $n$. The type of the $i$-th boss is $a_i$. If the $i$-th boss is easy then its type is $a_i = 0$, otherwise this boss is hard and its type is $a_i = 1$.

During one session, either you or your friend can kill one or two bosses (neither you nor your friend can skip the session, so the minimum number of bosses killed during one session is at least one). After your friend session, your session begins, then again your friend session begins, your session begins, and so on. The first session is your friend's session.

Your friend needs to get good because he can't actually kill hard bosses. To kill them, he uses skip points. One skip point can be used to kill one hard boss.

Your task is to find the minimum number of skip points your friend needs to use so you and your friend kill all $n$ bosses in the given order.

For example: suppose $n = 8$, $a = [1, 0, 1, 1, 0, 1, 1, 1]$. Then the best course of action is the following:

  your friend kills two first bosses, using one skip point for the first boss;  you kill the third and the fourth bosses;  your friend kills the fifth boss;  you kill the sixth and the seventh bosses;  your friend kills the last boss, using one skip point, so the tower is completed using two skip points. 

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of bosses. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1$), where $a_i$ is the type of the $i$-th boss.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer: the minimum number of skip points your friend needs to use so you and your friend kill all $n$ bosses in the given order.


-----Example-----
Input
6
8
1 0 1 1 0 1 1 1
5
1 1 1 1 0
7
1 1 1 1 0 0 1
6
1 1 1 1 1 1
1
1
1
0

Output
2
2
2
2
1
0