meetforever/GRPO_CL huggingface dataset:
user: Chef loves arrays. But he really loves a specific kind of them - Rainbow Arrays. 
The array is a Rainbow Array if it has such a structure:
- The first a1 elements equal to 1. 
- The next a2 elements equal to  2. 
- The next a3 elements equal to  3. 
- The next a4 elements equal to  4. 
- The next a5 elements equal to  5. 
- The next a6 elements equal to  6. 
- The next a7 elements equal to  7. 
- The next a6 elements equal to  6. 
- The next a5 elements equal to  5. 
- The next a4 elements equal to  4. 
- The next a3 elements equal to  3. 
- The next a2 elements equal to  2. 
- The next a1 elements equal to  1. 
- ai is a positive integer, the variables with the same index (a1 in the first statement and a1 in the last one, for example) are equal. 
- There are no any other elements in array. 

For example, {1,1,2,2,2,3,4,5,5,6,7,7,7,6,5,5,4,3,2,2,2,1,1} is a Rainbow Array.

The array {1,2,3,4,5,6,7,6,6,5,4,3,2,1} is not a Rainbow Array, because the sizes of the blocks with the element 6 are different. 
Please help Chef to count the number of different Rainbow Arrays that contain exactly N elements. 

-----Input-----
The first line contains a single integer N. 

-----Output-----
Output the number of different Rainbow Arrays with N elements, modulo 10^9+7. 

-----Constraints-----
- 1 ≤ N ≤ 106

-----Example-----
Input #1:
10 

Output #1:
0

Input #2:
13

Output #2:
1

Input #3:
14

Output #3:
1

Input #4:
15

Output #4:
7
user: You are given a non-empty string $s=s_1s_2\dots s_n$, which consists only of lowercase Latin letters. Polycarp does not like a string if it contains at least one string "one" or at least one string "two" (or both at the same time) as a substring. In other words, Polycarp does not like the string $s$ if there is an integer $j$ ($1 \le j \le n-2$), that $s_{j}s_{j+1}s_{j+2}=$"one" or $s_{j}s_{j+1}s_{j+2}=$"two".

For example:

  Polycarp does not like strings "oneee", "ontwow", "twone" and "oneonetwo" (they all have at least one substring "one" or "two"),  Polycarp likes strings "oonnee", "twwwo" and "twnoe" (they have no substrings "one" and "two"). 

Polycarp wants to select a certain set of indices (positions) and remove all letters on these positions. All removals are made at the same time.

For example, if the string looks like $s=$"onetwone", then if Polycarp selects two indices $3$ and $6$, then "onetwone" will be selected and the result is "ontwne".

What is the minimum number of indices (positions) that Polycarp needs to select to make the string liked? What should these positions be?


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Next, the test cases are given.

Each test case consists of one non-empty string $s$. Its length does not exceed $1.5\cdot10^5$. The string $s$ consists only of lowercase Latin letters.

It is guaranteed that the sum of lengths of all lines for all input data in the test does not exceed $1.5\cdot10^6$.


-----Output-----

Print an answer for each test case in the input in order of their appearance.

The first line of each answer should contain $r$ ($0 \le r \le |s|$) — the required minimum number of positions to be removed, where $|s|$ is the length of the given line. The second line of each answer should contain $r$ different integers — the indices themselves for removal in any order. Indices are numbered from left to right from $1$ to the length of the string. If $r=0$, then the second line can be skipped (or you can print empty). If there are several answers, print any of them.


-----Examples-----
Input
4
onetwone
testme
oneoneone
twotwo

Output
2
6 3
0

3
4 1 7 
2
1 4

Input
10
onetwonetwooneooonetwooo
two
one
twooooo
ttttwo
ttwwoo
ooone
onnne
oneeeee
oneeeeeeetwooooo

Output
6
18 11 12 1 6 21 
1
1 
1
3 
1
2 
1
6 
0

1
4 
0

1
1 
2
1 11 



-----Note-----

In the first example, answers are:

  "onetwone",  "testme" — Polycarp likes it, there is nothing to remove,  "oneoneone",  "twotwo". 

In the second example, answers are:   "onetwonetwooneooonetwooo",  "two",  "one",  "twooooo",  "ttttwo",  "ttwwoo" — Polycarp likes it, there is nothing to remove,  "ooone",  "onnne" — Polycarp likes it, there is nothing to remove,  "oneeeee",  "oneeeeeeetwooooo".
user: A tree is an undirected connected graph without cycles. The distance between two vertices is the number of edges in a simple path between them.

Limak is a little polar bear. He lives in a tree that consists of n vertices, numbered 1 through n.

Limak recently learned how to jump. He can jump from a vertex to any vertex within distance at most k.

For a pair of vertices (s, t) we define f(s, t) as the minimum number of jumps Limak needs to get from s to t. Your task is to find the sum of f(s, t) over all pairs of vertices (s, t) such that s < t.


-----Input-----

The first line of the input contains two integers n and k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ 5) — the number of vertices in the tree and the maximum allowed jump distance respectively.

The next n - 1 lines describe edges in the tree. The i-th of those lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n) — the indices on vertices connected with i-th edge.

It's guaranteed that the given edges form a tree.


-----Output-----

Print one integer, denoting the sum of f(s, t) over all pairs of vertices (s, t) such that s < t.


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

Output
20

Input
13 3
1 2
3 2
4 2
5 2
3 6
10 6
6 7
6 13
5 8
5 9
9 11
11 12

Output
114

Input
3 5
2 1
3 1

Output
3



-----Note-----

In the first sample, the given tree has 6 vertices and it's displayed on the drawing below. Limak can jump to any vertex within distance at most 2. For example, from the vertex 5 he can jump to any of vertices: 1, 2 and 4 (well, he can also jump to the vertex 5 itself). [Image] 

There are $\frac{n \cdot(n - 1)}{2} = 15$ pairs of vertices (s, t) such that s < t. For 5 of those pairs Limak would need two jumps: (1, 6), (3, 4), (3, 5), (3, 6), (5, 6). For other 10 pairs one jump is enough. So, the answer is 5·2 + 10·1 = 20.

In the third sample, Limak can jump between every two vertices directly. There are 3 pairs of vertices (s < t), so the answer is 3·1 = 3.
user: Let's say string $s$ has period $k$ if $s_i = s_{i + k}$ for all $i$ from $1$ to $|s| - k$ ($|s|$ means length of string $s$) and $k$ is the minimum positive integer with this property.

Some examples of a period: for $s$="0101" the period is $k=2$, for $s$="0000" the period is $k=1$, for $s$="010" the period is $k=2$, for $s$="0011" the period is $k=4$.

You are given string $t$ consisting only of 0's and 1's and you need to find such string $s$ that:  String $s$ consists only of 0's and 1's;  The length of $s$ doesn't exceed $2 \cdot |t|$;  String $t$ is a subsequence of string $s$;  String $s$ has smallest possible period among all strings that meet conditions 1—3. 

Let us recall that $t$ is a subsequence of $s$ if $t$ can be derived from $s$ by deleting zero or more elements (any) without changing the order of the remaining elements. For example, $t$="011" is a subsequence of $s$="10101".


-----Input-----

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

Next $T$ lines contain test cases — one per line. Each line contains string $t$ ($1 \le |t| \le 100$) consisting only of 0's and 1's.


-----Output-----

Print one string for each test case — string $s$ you needed to find. If there are multiple solutions print any one of them.


-----Example-----
Input
4
00
01
111
110

Output
00
01
11111
1010


-----Note-----

In the first and second test cases, $s = t$ since it's already one of the optimal solutions. Answers have periods equal to $1$ and $2$, respectively.

In the third test case, there are shorter optimal solutions, but it's okay since we don't need to minimize the string $s$. String $s$ has period equal to $1$.
user: The Rebel fleet is on the run. It consists of m ships currently gathered around a single planet. Just a few seconds ago, the vastly more powerful Empire fleet has appeared in the same solar system, and the Rebels will need to escape into hyperspace. In order to spread the fleet, the captain of each ship has independently come up with the coordinate to which that ship will jump. In the obsolete navigation system used by the Rebels, this coordinate is given as the value of an arithmetic expression of the form $\frac{a + b}{c}$.

To plan the future of the resistance movement, Princess Heidi needs to know, for each ship, how many ships are going to end up at the same coordinate after the jump. You are her only hope!


-----Input-----

The first line of the input contains a single integer m (1 ≤ m ≤ 200 000) – the number of ships. The next m lines describe one jump coordinate each, given as an arithmetic expression. An expression has the form (a+b)/c. Namely, it consists of: an opening parenthesis (, a positive integer a of up to two decimal digits, a plus sign +, a positive integer b of up to two decimal digits, a closing parenthesis ), a slash /, and a positive integer c of up to two decimal digits.


-----Output-----

Print a single line consisting of m space-separated integers. The i-th integer should be equal to the number of ships whose coordinate is equal to that of the i-th ship (including the i-th ship itself).


-----Example-----
Input
4
(99+98)/97
(26+4)/10
(12+33)/15
(5+1)/7

Output
1 2 2 1 


-----Note-----

In the sample testcase, the second and the third ship will both end up at the coordinate 3.

Note that this problem has only two versions – easy and hard.
user: You are given an array $a_1, a_2, \dots, a_n$ and an integer $k$.

You are asked to divide this array into $k$ non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray. Let $f(i)$ be the index of subarray the $i$-th element belongs to. Subarrays are numbered from left to right and from $1$ to $k$.

Let the cost of division be equal to $\sum\limits_{i=1}^{n} (a_i \cdot f(i))$. For example, if $a = [1, -2, -3, 4, -5, 6, -7]$ and we divide it into $3$ subbarays in the following way: $[1, -2, -3], [4, -5], [6, -7]$, then the cost of division is equal to $1 \cdot 1 - 2 \cdot 1 - 3 \cdot 1 + 4 \cdot 2 - 5 \cdot 2 + 6 \cdot 3 - 7 \cdot 3 = -9$.

Calculate the maximum cost you can obtain by dividing the array $a$ into $k$ non-empty consecutive subarrays. 


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($ |a_i| \le 10^6$). 


-----Output-----

Print the maximum cost you can obtain by dividing the array $a$ into $k$ nonempty consecutive subarrays. 


-----Examples-----
Input
5 2
-1 -2 5 -4 8

Output
15

Input
7 6
-3 0 -1 -2 -2 -4 -1

Output
-45

Input
4 1
3 -1 6 0

Output
8
user: Alice has a cute cat. To keep her cat fit, Alice wants to design an exercising walk for her cat! 

Initially, Alice's cat is located in a cell $(x,y)$ of an infinite grid. According to Alice's theory, cat needs to move:   exactly $a$ steps left: from $(u,v)$ to $(u-1,v)$;  exactly $b$ steps right: from $(u,v)$ to $(u+1,v)$;  exactly $c$ steps down: from $(u,v)$ to $(u,v-1)$;  exactly $d$ steps up: from $(u,v)$ to $(u,v+1)$. 

Note that the moves can be performed in an arbitrary order. For example, if the cat has to move $1$ step left, $3$ steps right and $2$ steps down, then the walk right, down, left, right, right, down is valid.

Alice, however, is worrying that her cat might get lost if it moves far away from her. So she hopes that her cat is always in the area $[x_1,x_2]\times [y_1,y_2]$, i.e. for every cat's position $(u,v)$ of a walk $x_1 \le u \le x_2$ and $y_1 \le v \le y_2$ holds.

Also, note that the cat can visit the same cell multiple times.

Can you help Alice find out if there exists a walk satisfying her wishes?

Formally, the walk should contain exactly $a+b+c+d$ unit moves ($a$ to the left, $b$ to the right, $c$ to the down, $d$ to the up). Alice can do the moves in any order. Her current position $(u, v)$ should always satisfy the constraints: $x_1 \le u \le x_2$, $y_1 \le v \le y_2$. The staring point is $(x, y)$.

You are required to answer $t$ test cases independently.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of testcases. 

The first line of each test case contains four integers $a$, $b$, $c$, $d$ ($0 \le a,b,c,d \le 10^8$, $a+b+c+d \ge 1$).

The second line of the test case contains six integers $x$, $y$, $x_1$, $y_1$, $x_2$, $y_2$ ($-10^8 \le x_1\le x \le x_2 \le 10^8$, $-10^8 \le y_1 \le y \le y_2 \le 10^8$).


-----Output-----

For each test case, output "YES" in a separate line, if there exists a walk satisfying her wishes. Otherwise, output "NO" in a separate line. 

You can print each letter in any case (upper or lower).


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

Output
Yes
No
No
Yes
Yes
Yes



-----Note-----

In the first test case, one valid exercising walk is $$(0,0)\rightarrow (-1,0) \rightarrow (-2,0)\rightarrow (-2,1) \rightarrow (-2,2)\rightarrow (-1,2)\rightarrow(0,2)\rightarrow (0,1)\rightarrow (0,0) \rightarrow (-1,0)$$
user: Alice and Bob play a game. Initially they have a string $s_1, s_2, \dots, s_n$, consisting of only characters . and X. They take alternating turns, and Alice is moving first. During each turn, the player has to select a contiguous substring consisting only of characters . and replaces each of them with X. Alice must select a substing of length $a$, and Bob must select a substring of length $b$. It is guaranteed that $a > b$.

For example, if $s =$ ...X.. and $a = 3$, $b = 2$, then after Alice's move string can turn only into XXXX... And if it's Bob's turn and the string $s =$ ...X.., then after Bob's move the string can turn into XX.X.., .XXX.. or ...XXX.

Whoever is unable to make a move, loses. You have to determine who wins if they both play optimally.

You have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.

The first line of each query contains two integers $a$ and $b$ ($1 \le b < a \le 3 \cdot 10^5$).

The second line of each query contains the string $s$ ($1 \le |s| \le 3 \cdot 10^5$), consisting of only characters . and X.

It is guaranteed that sum of all $|s|$ over all queries not exceed $3 \cdot 10^5$.


-----Output-----

For each test case print YES if Alice can win 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
3
3 2
XX......XX...X
4 2
X...X.X..X
5 3
.......X..X

Output
YES
NO
YES



-----Note-----

In the first query Alice can select substring $s_3 \dots s_5$. After that $s$ turns into XXXXX...XX...X. After that, no matter what move Bob makes, Alice can make the move (this will be her second move), but Bob can't make his second move.

In the second query Alice can not win because she cannot even make one move.

In the third query Alice can choose substring $s_2 \dots s_6$. After that $s$ turns into .XXXXX.X..X, and Bob can't make a move after that.
user: DLS and JLS are bored with a Math lesson. In order to entertain themselves, DLS took a sheet of paper and drew $n$ distinct lines, given by equations $y = x + p_i$ for some distinct $p_1, p_2, \ldots, p_n$.

Then JLS drew on the same paper sheet $m$ distinct lines given by equations $y = -x + q_i$ for some distinct $q_1, q_2, \ldots, q_m$.

DLS and JLS are interested in counting how many line pairs have integer intersection points, i.e. points with both coordinates that are integers. Unfortunately, the lesson will end up soon, so DLS and JLS are asking for your help.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$), the number of test cases in the input. Then follow the test case descriptions.

The first line of a test case contains an integer $n$ ($1 \le n \le 10^5$), the number of lines drawn by DLS.

The second line of a test case contains $n$ distinct integers $p_i$ ($0 \le p_i \le 10^9$) describing the lines drawn by DLS. The integer $p_i$ describes a line given by the equation $y = x + p_i$.

The third line of a test case contains an integer $m$ ($1 \le m \le 10^5$), the number of lines drawn by JLS.

The fourth line of a test case contains $m$ distinct integers $q_i$ ($0 \le q_i \le 10^9$) describing the lines drawn by JLS. The integer $q_i$ describes a line given by the equation $y = -x + q_i$.

The sum of the values of $n$ over all test cases in the input does not exceed $10^5$. Similarly, the sum of the values of $m$ over all test cases in the input does not exceed $10^5$.

In hacks it is allowed to use only one test case in the input, so $t=1$ should be satisfied.


-----Output-----

For each test case in the input print a single integer — the number of line pairs with integer intersection points. 


-----Example-----
Input
3
3
1 3 2
2
0 3
1
1
1
1
1
2
1
1

Output
3
1
0



-----Note-----

The picture shows the lines from the first test case of the example. Black circles denote intersection points with integer coordinates. [Image]
user: Heidi got one brain, thumbs up! But the evening isn't over yet and one more challenge awaits our dauntless agent: after dinner, at precisely midnight, the N attendees love to play a very risky game...

Every zombie gets a number n_{i} (1 ≤ n_{i} ≤ N) written on his forehead. Although no zombie can see his own number, he can see the numbers written on the foreheads of all N - 1 fellows. Note that not all numbers have to be unique (they can even all be the same). From this point on, no more communication between zombies is allowed. Observation is the only key to success. When the cuckoo clock strikes midnight, all attendees have to simultaneously guess the number on their own forehead. If at least one of them guesses his number correctly, all zombies survive and go home happily. On the other hand, if not a single attendee manages to guess his number correctly, all of them are doomed to die!

Zombies aren't very bright creatures though, and Heidi has to act fast if she does not want to jeopardize her life. She has one single option: by performing some quick surgery on the brain she managed to get from the chest, she has the ability to remotely reprogram the decision-making strategy of all attendees for their upcoming midnight game! Can you suggest a sound strategy to Heidi which, given the rules of the game, ensures that at least one attendee will guess his own number correctly, for any possible sequence of numbers on the foreheads?

Given a zombie's rank R and the N - 1 numbers n_{i} on the other attendees' foreheads, your program will have to return the number that the zombie of rank R shall guess. Those answers define your strategy, and we will check if it is flawless or not.


-----Input-----

The first line of input contains a single integer T (1 ≤ T ≤ 50000): the number of scenarios for which you have to make a guess.

The T scenarios follow, described on two lines each:   The first line holds two integers, N (2 ≤ N ≤ 6), the number of attendees, and R (1 ≤ R ≤ N), the rank of the zombie who has to make the guess.  The second line lists N - 1 integers: the numbers on the foreheads of all other attendees, listed in increasing order of the attendees' rank. (Every zombie knows the rank of every other zombie.) 


-----Output-----

For every scenario, output a single integer: the number that the zombie of rank R shall guess, based on the numbers n_{i} on his N - 1 fellows' foreheads.


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

Output
1
2
2
1

Input
2
5 2
2 2 2 2
6 4
3 2 6 1 2

Output
5
2



-----Note-----

For instance, if there were N = 2 two attendees, a successful strategy could be:   The zombie of rank 1 always guesses the number he sees on the forehead of the zombie of rank 2.  The zombie of rank 2 always guesses the opposite of the number he sees on the forehead of the zombie of rank 1.
user: Nikolay has only recently started in competitive programming, but already qualified to the finals of one prestigious olympiad. There going to be $n$ participants, one of whom is Nikolay. Like any good olympiad, it consists of two rounds. Tired of the traditional rules, in which the participant who solved the largest number of problems wins, the organizers came up with different rules.

Suppose in the first round participant A took $x$-th place and in the second round — $y$-th place. Then the total score of the participant A is sum $x + y$. The overall place of the participant A is the number of participants (including A) having their total score less than or equal to the total score of A. Note, that some participants may end up having a common overall place. It is also important to note, that in both the first and the second round there were no two participants tying at a common place. In other words, for every $i$ from $1$ to $n$ exactly one participant took $i$-th place in first round and exactly one participant took $i$-th place in second round.

Right after the end of the Olympiad, Nikolay was informed that he got $x$-th place in first round and $y$-th place in the second round. Nikolay doesn't know the results of other participants, yet he wonders what is the minimum and maximum place he can take, if we consider the most favorable and unfavorable outcome for him. Please help Nikolay to find the answer to this question.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases to solve.

Each of the following $t$ lines contains integers $n$, $x$, $y$ ($1 \leq n \leq 10^9$, $1 \le x, y \le n$) — the number of participants in the olympiad, the place that Nikolay took in the first round and the place that Nikolay took in the second round.


-----Output-----

Print two integers — the minimum and maximum possible overall place Nikolay could take.


-----Examples-----
Input
1
5 1 3

Output
1 3

Input
1
6 3 4

Output
2 6



-----Note-----

Explanation for the first example:

Suppose there were 5 participants A-E. Let's denote Nikolay as A. The the most favorable results for Nikolay could look as follows: $\left. \begin{array}{|c|c|c|c|c|} \hline \text{Participant} & {\text{Round 1}} & {\text{Round 2}} & {\text{Total score}} & {\text{Place}} \\ \hline A & {1} & {3} & {4} & {1} \\ \hline B & {2} & {4} & {6} & {3} \\ \hline C & {3} & {5} & {8} & {5} \\ \hline D & {4} & {1} & {5} & {2} \\ \hline E & {5} & {2} & {7} & {4} \\ \hline \end{array} \right.$ 

However, the results of the Olympiad could also look like this: $\left. \begin{array}{|c|c|c|c|c|} \hline \text{Participant} & {\text{Round 1}} & {\text{Round 2}} & {\text{Total score}} & {\text{Place}} \\ \hline A & {1} & {3} & {4} & {3} \\ \hline B & {2} & {2} & {4} & {3} \\ \hline C & {3} & {1} & {4} & {3} \\ \hline D & {4} & {4} & {8} & {4} \\ \hline E & {5} & {5} & {10} & {5} \\ \hline \end{array} \right.$ 

In the first case Nikolay would have taken first place, and in the second — third place.