meetforever/GRPO_CL huggingface dataset:
user: There are N empty boxes arranged in a row from left to right.
The integer i is written on the i-th box from the left (1 \leq i \leq N).
For each of these boxes, Snuke can choose either to put a ball in it or to put nothing in it.
We say a set of choices to put a ball or not in the boxes is good when the following condition is satisfied:
 - For every integer i between 1 and N (inclusive), the total number of balls contained in the boxes with multiples of i written on them is congruent to a_i modulo 2.
Does there exist a good set of choices? If the answer is yes, find one good set of choices.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2 \times 10^5
 - a_i is 0 or 1.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 a_2 ... a_N

-----Output-----
If a good set of choices does not exist, print -1.
If a good set of choices exists, print one such set of choices in the following format:
M
b_1 b_2 ... b_M

where M denotes the number of boxes that will contain a ball, and b_1,\ b_2,\ ...,\ b_M are the integers written on these boxes, in any order.

-----Sample Input-----
3
1 0 0

-----Sample Output-----
1
1

Consider putting a ball only in the box with 1 written on it.
 - There are three boxes with multiples of 1 written on them: the boxes with 1, 2, and 3. The total number of balls contained in these boxes is 1.
 - There is only one box with a multiple of 2 written on it: the box with 2. The total number of balls contained in these boxes is 0.
 - There is only one box with a multiple of 3 written on it: the box with 3. The total number of balls contained in these boxes is 0.
Thus, the condition is satisfied, so this set of choices is good.
user: There are N mountains in a circle, called Mountain 1, Mountain 2, ..., Mountain N in clockwise order. N is an odd number.
Between these mountains, there are N dams, called Dam 1, Dam 2, ..., Dam N. Dam i (1 \leq i \leq N) is located between Mountain i and i+1 (Mountain N+1 is Mountain 1).
When Mountain i (1 \leq i \leq N) receives 2x liters of rain, Dam i-1 and Dam i each accumulates x liters of water (Dam 0 is Dam N).
One day, each of the mountains received a non-negative even number of liters of rain.
As a result, Dam i (1 \leq i \leq N) accumulated a total of A_i liters of water.
Find the amount of rain each of the mountains received. We can prove that the solution is unique under the constraints of this problem.

-----Constraints-----
 - All values in input are integers.
 - 3 \leq N \leq 10^5-1
 - N is an odd number.
 - 0 \leq A_i \leq 10^9
 - The situation represented by input can occur when each of the mountains receives a non-negative even number of liters of rain.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print N integers representing the number of liters of rain Mountain 1, Mountain 2, ..., Mountain N received, in this order.

-----Sample Input-----
3
2 2 4

-----Sample Output-----
4 0 4

If we assume Mountain 1, 2, and 3 received 4, 0, and 4 liters of rain, respectively, it is consistent with this input, as follows:
 - Dam 1 should have accumulated \frac{4}{2} + \frac{0}{2} = 2 liters of water.
 - Dam 2 should have accumulated \frac{0}{2} + \frac{4}{2} = 2 liters of water.
 - Dam 3 should have accumulated \frac{4}{2} + \frac{4}{2} = 4 liters of water.
user: Theater stage is a rectangular field of size n × m. The director gave you the stage's plan which actors will follow. For each cell it is stated in the plan if there would be an actor in this cell or not.

You are to place a spotlight on the stage in some good position. The spotlight will project light in one of the four directions (if you look at the stage from above) — left, right, up or down. Thus, the spotlight's position is a cell it is placed to and a direction it shines.

A position is good if two conditions hold:   there is no actor in the cell the spotlight is placed to;  there is at least one actor in the direction the spotlight projects. 

Count the number of good positions for placing the spotlight. Two positions of spotlight are considered to be different if the location cells or projection direction differ.


-----Input-----

The first line contains two positive integers n and m (1 ≤ n, m ≤ 1000) — the number of rows and the number of columns in the plan.

The next n lines contain m integers, 0 or 1 each — the description of the plan. Integer 1, means there will be an actor in the corresponding cell, while 0 means the cell will remain empty. It is guaranteed that there is at least one actor in the plan.


-----Output-----

Print one integer — the number of good positions for placing the spotlight.


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

Output
9

Input
4 4
0 0 0 0
1 0 0 1
0 1 1 0
0 1 0 0

Output
20



-----Note-----

In the first example the following positions are good:  the (1, 1) cell and right direction;  the (1, 1) cell and down direction;  the (1, 3) cell and left direction;  the (1, 3) cell and down direction;  the (1, 4) cell and left direction;  the (2, 2) cell and left direction;  the (2, 2) cell and up direction;  the (2, 2) and right direction;  the (2, 4) cell and left direction. 

Therefore, there are 9 good positions in this example.
user: Let's define a forest as a non-directed acyclic graph (also without loops and parallel edges). One day Misha played with the forest consisting of n vertices. For each vertex v from 0 to n - 1 he wrote down two integers, degree_{v} and s_{v}, were the first integer is the number of vertices adjacent to vertex v, and the second integer is the XOR sum of the numbers of vertices adjacent to v (if there were no adjacent vertices, he wrote down 0). 

Next day Misha couldn't remember what graph he initially had. Misha has values degree_{v} and s_{v} left, though. Help him find the number of edges and the edges of the initial graph. It is guaranteed that there exists a forest that corresponds to the numbers written by Misha.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2^16), the number of vertices in the graph.

The i-th of the next lines contains numbers degree_{i} and s_{i} (0 ≤ degree_{i} ≤ n - 1, 0 ≤ s_{i} < 2^16), separated by a space.


-----Output-----

In the first line print number m, the number of edges of the graph.

Next print m lines, each containing two distinct numbers, a and b (0 ≤ a ≤ n - 1, 0 ≤ b ≤ n - 1), corresponding to edge (a, b).

Edges can be printed in any order; vertices of the edge can also be printed in any order.


-----Examples-----
Input
3
2 3
1 0
1 0

Output
2
1 0
2 0

Input
2
1 1
1 0

Output
1
0 1



-----Note-----

The XOR sum of numbers is the result of bitwise adding numbers modulo 2. This operation exists in many modern programming languages. For example, in languages C++, Java and Python it is represented as "^", and in Pascal — as "xor".
user: Inna loves digit 9 very much. That's why she asked Dima to write a small number consisting of nines. But Dima must have misunderstood her and he wrote a very large number a, consisting of digits from 1 to 9.

Inna wants to slightly alter the number Dima wrote so that in the end the number contained as many digits nine as possible. In one move, Inna can choose two adjacent digits in a number which sum equals 9 and replace them by a single digit 9.

For instance, Inna can alter number 14545181 like this: 14545181 → 1945181 → 194519 → 19919. Also, she can use this method to transform number 14545181 into number 19991. Inna will not transform it into 149591 as she can get numbers 19919 and 19991 which contain more digits nine.

Dima is a programmer so he wants to find out how many distinct numbers containing as many digits nine as possible Inna can get from the written number. Help him with this challenging task.


-----Input-----

The first line of the input contains integer a (1 ≤ a ≤ 10^100000). Number a doesn't have any zeroes.


-----Output-----

In a single line print a single integer — the answer to the problem. It is guaranteed that the answer to the problem doesn't exceed 2^63 - 1.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
369727

Output
2

Input
123456789987654321

Output
1

Input
1

Output
1



-----Note-----

Notes to the samples

In the first sample Inna can get the following numbers: 369727 → 99727 → 9997, 369727 → 99727 → 9979.

In the second sample, Inna can act like this: 123456789987654321 → 12396789987654321 → 1239678998769321.
user: The police department of your city has just started its journey. Initially, they don’t have any manpower. So, they started hiring new recruits in groups.

Meanwhile, crimes keeps occurring within the city. One member of the police force can investigate only one crime during his/her lifetime.

If there is no police officer free (isn't busy with crime) during the occurrence of a crime, it will go untreated.

Given the chronological order of crime occurrences and recruit hirings, find the number of crimes which will go untreated.


-----Input-----

The first line of input will contain an integer n (1 ≤ n ≤ 10^5), the number of events. The next line will contain n space-separated integers.

If the integer is -1 then it means a crime has occurred. Otherwise, the integer will be positive, the number of officers recruited together at that time. No more than 10 officers will be recruited at a time.


-----Output-----

Print a single integer, the number of crimes which will go untreated.


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

Output
2

Input
8
1 -1 1 -1 -1 1 1 1

Output
1

Input
11
-1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1

Output
8



-----Note-----

Lets consider the second example:  Firstly one person is hired.  Then crime appears, the last hired person will investigate this crime.  One more person is hired.  One more crime appears, the last hired person will investigate this crime.  Crime appears. There is no free policeman at the time, so this crime will go untreated.  One more person is hired.  One more person is hired.  One more person is hired. 

The answer is one, as one crime (on step 5) will go untreated.
user: While walking down the street Vanya saw a label "Hide&Seek". Because he is a programmer, he used & as a bitwise AND for these two words represented as a integers in base 64 and got new word. Now Vanya thinks of some string s and wants to know the number of pairs of words of length |s| (length of s), such that their bitwise AND is equal to s. As this number can be large, output it modulo 10^9 + 7.

To represent the string as a number in numeral system with base 64 Vanya uses the following rules:  digits from '0' to '9' correspond to integers from 0 to 9;  letters from 'A' to 'Z' correspond to integers from 10 to 35;  letters from 'a' to 'z' correspond to integers from 36 to 61;  letter '-' correspond to integer 62;  letter '_' correspond to integer 63. 


-----Input-----

The only line of the input contains a single word s (1 ≤ |s| ≤ 100 000), consisting of digits, lowercase and uppercase English letters, characters '-' and '_'.


-----Output-----

Print a single integer — the number of possible pairs of words, such that their bitwise AND is equal to string s modulo 10^9 + 7.


-----Examples-----
Input
z

Output
3

Input
V_V

Output
9

Input
Codeforces

Output
130653412



-----Note-----

For a detailed definition of bitwise AND we recommend to take a look in the corresponding article in Wikipedia.

In the first sample, there are 3 possible solutions:   z&_ = 61&63 = 61 = z  _&z = 63&61 = 61 = z  z&z = 61&61 = 61 = z
user: This problem is given in two versions that differ only by constraints. If you can solve this problem in large constraints, then you can just write a single solution to the both versions. If you find the problem too difficult in large constraints, you can write solution to the simplified version only.

Waking up in the morning, Apollinaria decided to bake cookies. To bake one cookie, she needs n ingredients, and for each ingredient she knows the value a_{i} — how many grams of this ingredient one needs to bake a cookie. To prepare one cookie Apollinaria needs to use all n ingredients.

Apollinaria has b_{i} gram of the i-th ingredient. Also she has k grams of a magic powder. Each gram of magic powder can be turned to exactly 1 gram of any of the n ingredients and can be used for baking cookies.

Your task is to determine the maximum number of cookies, which Apollinaria is able to bake using the ingredients that she has and the magic powder.


-----Input-----

The first line of the input contains two positive integers n and k (1 ≤ n, k ≤ 1000) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000), where the i-th number is equal to the number of grams of the i-th ingredient, needed to bake one cookie.

The third line contains the sequence b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 1000), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.


-----Output-----

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.


-----Examples-----
Input
3 1
2 1 4
11 3 16

Output
4

Input
4 3
4 3 5 6
11 12 14 20

Output
3



-----Note-----

In the first sample it is profitably for Apollinaria to make the existing 1 gram of her magic powder to ingredient with the index 2, then Apollinaria will be able to bake 4 cookies.

In the second sample Apollinaria should turn 1 gram of magic powder to ingredient with the index 1 and 1 gram of magic powder to ingredient with the index 3. Then Apollinaria will be able to bake 3 cookies. The remaining 1 gram of the magic powder can be left, because it can't be used to increase the answer.
user: You are given a sequence of numbers a_1, a_2, ..., a_{n}, and a number m.

Check if it is possible to choose a non-empty subsequence a_{i}_{j} such that the sum of numbers in this subsequence is divisible by m.


-----Input-----

The first line contains two numbers, n and m (1 ≤ n ≤ 10^6, 2 ≤ m ≤ 10^3) — the size of the original sequence and the number such that sum should be divisible by it.

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9).


-----Output-----

In the single line print either "YES" (without the quotes) if there exists the sought subsequence, or "NO" (without the quotes), if such subsequence doesn't exist.


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

Output
YES

Input
1 6
5

Output
NO

Input
4 6
3 1 1 3

Output
YES

Input
6 6
5 5 5 5 5 5

Output
YES



-----Note-----

In the first sample test you can choose numbers 2 and 3, the sum of which is divisible by 5.

In the second sample test the single non-empty subsequence of numbers is a single number 5. Number 5 is not divisible by 6, that is, the sought subsequence doesn't exist.

In the third sample test you need to choose two numbers 3 on the ends.

In the fourth sample test you can take the whole subsequence.
user: Pavel has several sticks with lengths equal to powers of two.

He has $a_0$ sticks of length $2^0 = 1$, $a_1$ sticks of length $2^1 = 2$, ..., $a_{n-1}$ sticks of length $2^{n-1}$. 

Pavel wants to make the maximum possible number of triangles using these sticks. The triangles should have strictly positive area, each stick can be used in at most one triangle.

It is forbidden to break sticks, and each triangle should consist of exactly three sticks.

Find the maximum possible number of triangles.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 300\,000$) — the number of different lengths of sticks.

The second line contains $n$ integers $a_0$, $a_1$, ..., $a_{n-1}$ ($1 \leq a_i \leq 10^9$), where $a_i$ is the number of sticks with the length equal to $2^i$.


-----Output-----

Print a single integer — the maximum possible number of non-degenerate triangles that Pavel can make.


-----Examples-----
Input
5
1 2 2 2 2

Output
3

Input
3
1 1 1

Output
0

Input
3
3 3 3

Output
3



-----Note-----

In the first example, Pavel can, for example, make this set of triangles (the lengths of the sides of the triangles are listed): $(2^0, 2^4, 2^4)$, $(2^1, 2^3, 2^3)$, $(2^1, 2^2, 2^2)$.

In the second example, Pavel cannot make a single triangle.

In the third example, Pavel can, for example, create this set of triangles (the lengths of the sides of the triangles are listed): $(2^0, 2^0, 2^0)$, $(2^1, 2^1, 2^1)$, $(2^2, 2^2, 2^2)$.
user: Smart Beaver decided to be not only smart, but also a healthy beaver! And so he began to attend physical education classes at school X. In this school, physical education has a very creative teacher. One of his favorite warm-up exercises is throwing balls. Students line up. Each one gets a single ball in the beginning. The balls are numbered from 1 to n (by the demand of the inventory commission). [Image]  Figure 1. The initial position for n = 5.  

After receiving the balls the students perform the warm-up exercise. The exercise takes place in a few throws. For each throw the teacher chooses any two arbitrary different students who will participate in it. The selected students throw their balls to each other. Thus, after each throw the students remain in their positions, and the two balls are swapped. [Image]  Figure 2. The example of a throw.  

In this case there was a throw between the students, who were holding the 2-nd and the 4-th balls. Since the warm-up has many exercises, each of them can only continue for little time. Therefore, for each student we know the maximum number of throws he can participate in. For this lessons maximum number of throws will be 1 or 2.

Note that after all phases of the considered exercise any ball can end up with any student. Smart Beaver decided to formalize it and introduced the concept of the "ball order". The ball order is a sequence of n numbers that correspond to the order of balls in the line. The first number will match the number of the ball of the first from the left student in the line, the second number will match the ball of the second student, and so on. For example, in figure 2 the order of the balls was (1, 2, 3, 4, 5), and after the throw it was (1, 4, 3, 2, 5). Smart beaver knows the number of students and for each student he knows the maximum number of throws in which he can participate. And now he is wondering: what is the number of distinct ways of ball orders by the end of the exercise.


-----Input-----

The first line contains a single number n — the number of students in the line and the number of balls. The next line contains exactly n space-separated integers. Each number corresponds to a student in the line (the i-th number corresponds to the i-th from the left student in the line) and shows the number of throws he can participate in.

The input limits for scoring 30 points are (subproblem D1):   1 ≤ n ≤ 10. 

The input limits for scoring 70 points are (subproblems D1+D2):   1 ≤ n ≤ 500. 

The input limits for scoring 100 points are (subproblems D1+D2+D3):   1 ≤ n ≤ 1000000. 


-----Output-----

The output should contain a single integer — the number of variants of ball orders after the warm up exercise is complete. As the number can be rather large, print it modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
5
1 2 2 1 2

Output
120

Input
8
1 2 2 1 2 1 1 2

Output
16800
user: In this task you need to process a set of stock exchange orders and use them to create order book.

An order is an instruction of some participant to buy or sell stocks on stock exchange. The order number i has price p_{i}, direction d_{i} — buy or sell, and integer q_{i}. This means that the participant is ready to buy or sell q_{i} stocks at price p_{i} for one stock. A value q_{i} is also known as a volume of an order.

All orders with the same price p and direction d are merged into one aggregated order with price p and direction d. The volume of such order is a sum of volumes of the initial orders.

An order book is a list of aggregated orders, the first part of which contains sell orders sorted by price in descending order, the second contains buy orders also sorted by price in descending order.

An order book of depth s contains s best aggregated orders for each direction. A buy order is better if it has higher price and a sell order is better if it has lower price. If there are less than s aggregated orders for some direction then all of them will be in the final order book.

You are given n stock exhange orders. Your task is to print order book of depth s for these orders.


-----Input-----

The input starts with two positive integers n and s (1 ≤ n ≤ 1000, 1 ≤ s ≤ 50), the number of orders and the book depth.

Next n lines contains a letter d_{i} (either 'B' or 'S'), an integer p_{i} (0 ≤ p_{i} ≤ 10^5) and an integer q_{i} (1 ≤ q_{i} ≤ 10^4) — direction, price and volume respectively. The letter 'B' means buy, 'S' means sell. The price of any sell order is higher than the price of any buy order.


-----Output-----

Print no more than 2s lines with aggregated orders from order book of depth s. The output format for orders should be the same as in input.


-----Examples-----
Input
6 2
B 10 3
S 50 2
S 40 1
S 50 6
B 20 4
B 25 10

Output
S 50 8
S 40 1
B 25 10
B 20 4



-----Note-----

Denote (x, y) an order with price x and volume y. There are 3 aggregated buy orders (10, 3), (20, 4), (25, 10) and two sell orders (50, 8), (40, 1) in the sample.

You need to print no more than two best orders for each direction, so you shouldn't print the order (10 3) having the worst price among buy orders.