vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In this task, we would like for you to appreciate the usefulness of the groupby() function of itertools . To read more about this function, Check this out .

You are given a string $\mbox{S}$. Suppose a character '$\textbf{C}$' occurs consecutively $\mbox{X}$ times in the string. Replace these consecutive occurrences of the character '$\textbf{C}$' with $(X,c)$ in the string. 

For a better understanding of the problem, check the explanation. 

Input Format

A single line of input consisting of the string $\mbox{S}$. 

Output Format 

A single line of output consisting of the modified string.

Constraints

All the characters of $\mbox{S}$ denote integers between $\mbox{o}$ and $\mbox{9}$. 

$1\leq\big|\text{}S\big|\leq10^4$

Sample Input

1222311

Sample Output

(1, 1) (3, 2) (1, 3) (2, 1)

Explanation

First, the character $\mbox{I}$ occurs only once. It is replaced by $(1,\:\:1)$. Then the character $2$ occurs three times, and it is replaced by $(3,2)$ and so on. 

Also, note the single space within each compression and between the compressions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let $f_{x} = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}$ for $x \ge 4$.

You have given integers $n$, $f_{1}$, $f_{2}$, $f_{3}$, and $c$. Find $f_{n} \bmod (10^{9}+7)$.


-----Input-----

The only line contains five integers $n$, $f_{1}$, $f_{2}$, $f_{3}$, and $c$ ($4 \le n \le 10^{18}$, $1 \le f_{1}$, $f_{2}$, $f_{3}$, $c \le 10^{9}$).


-----Output-----

Print $f_{n} \bmod (10^{9} + 7)$.


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

Output
72900

Input
17 97 41 37 11

Output
317451037



-----Note-----

In the first example, $f_{4} = 90$, $f_{5} = 72900$.

In the second example, $f_{17} \approx 2.28 \times 10^{29587}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a grid of size M X N.  Each point of the grid could be free, occupied by a black marble or by a white marble. If a black marble is placed at point (x,y) then no other black marble could be placed at points (x-2, y-2), (x-2, y+2), (x+2, y-2) and (x+2, y+2) unless there is a white marble exactly in the middle.

Ex: We could place two black marbles  at point (x,y) and (x+2,y+2) if and only if there is a white marble at point (x+1,y+1).

Given a grid with some points which has been occupied by black marbles or white marbles your task is to find out the greatest number of black marbles to add to this grid satisfying rules above. Note that we can put a black marble at a free point, but we cannot remove any black marble and white marble, and we cannot add white marble.

Input

There are several test cases, each formed as follows:

i) The first line contains two positive integer M, N.

ii) Next M lines, each contains N characters (no spaces) of {'F', 'G', 'P'} (ASCII: #70, #71, #80), the j-th character of the i-th line represents the point (i-1, j-1) on the grid: 'F' is a free point, 'G' is occupied by a black marble and 'P' is occupied by a white marble.

The input is ended with M = N = 0.

Output

For each test case, output on a line the greatest number of black marbles which can be added to the given grid.

Constraints

M>0,  N<701

The sum of MxN does not exceed 490000 in one judge file. 

SAMPLE INPUT
3 4
FPFP
PFPP
GFFG
2 3
PFP
GPF
0 0

SAMPLE OUTPUT
3
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Based on a peculiar incident at basketball practice, Akari came up with the following competitive programming problem!

You are given n points on the plane, no three of which are collinear. The i-th point initially has a label a_i, in such a way that the labels a_1, a_2, ..., a_n form a permutation of 1, 2, ..., n.

You are allowed to modify the labels through the following operation:

  1. Choose two distinct integers i and j between 1 and n. 
  2. Swap the labels of points i and j, and finally 
  3. Draw the segment between points i and j. 



A sequence of operations is valid if after applying all of the operations in the sequence in order, the k-th point ends up having the label k for all k between 1 and n inclusive, and the drawn segments don't intersect each other internally. Formally, if two of the segments intersect, then they must do so at a common endpoint of both segments.

In particular, all drawn segments must be distinct.

Find any valid sequence of operations, or say that none exist. 

Input

The first line contains an integer n (3 ≤ n ≤ 2000) — the number of points.

The i-th of the following n lines contains three integers x_i, y_i, a_i (-10^6 ≤ x_i, y_i ≤ 10^6, 1 ≤ a_i ≤ n), representing that the i-th point has coordinates (x_i, y_i) and initially has label a_i.

It is guaranteed that all points are distinct, no three points are collinear, and the labels a_1, a_2, ..., a_n form a permutation of 1, 2, ..., n.

Output

If it is impossible to perform a valid sequence of operations, print -1.

Otherwise, print an integer k (0 ≤ k ≤ (n(n - 1))/(2)) — the number of operations to perform, followed by k lines, each containing two integers i and j (1 ≤ i, j ≤ n, i≠ j) — the indices of the points chosen for the operation.

Note that you are not required to minimize or maximize the value of k.

If there are multiple possible answers, you may print any of them.

Examples

Input


5
-1 -2 2
3 0 5
1 3 4
4 -3 3
5 2 1


Output


5
1 2
5 3
4 5
1 5
1 3


Input


3
5 4 1
0 0 2
-3 -2 3


Output


0

Note

The following animation showcases the first sample test case. The black numbers represent the indices of the points, while the boxed orange numbers represent their labels.

<image>

In the second test case, all labels are already in their correct positions, so no operations are necessary.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A group of friends snuck away from their school campus, but now they must return from the main campus gate to their dorm while remaining undetected by the many teachers who patrol the campus. Fortunately, they have an invisibility cloak, but it is only large enough to cover two people at a time. They will take turns as individuals or pairs traveling across campus under the cloak (and by necessity, returning the cloak to the gate if others remain). Each student has a maximum pace at which he or she is able to travel, yet if a pair of students are walking under the cloak together, they will have to travel at the pace of the slower of the two. Their goal is to have everyone back at the dorm as quickly as possible.

As an example, assume that there are four people in the group, with person A able to make the trip in $1$ minute, person B able to travel in $2$ minutes, person C able to travel in $7$ minutes, and person D able to travel in $10$ minutes. It is possible to get everyone to the dorm in $17$ minutes with the following plan:


– A and B go from the gate to the dorm together

(taking $2$ minutes)

– A returns with the cloak to the gate

(taking $1$ minute)

– C and D go from the gate to the dorm together

(taking $10$ minutes)

– B returns with the cloak to the gate

(taking $2$ minutes)

– A and B go from the gate to the dorm together

(taking $2$ minutes)

-----Input-----
The input is a single line beginning with an integer, $2 \leq N \leq 15$. Following that are $N$ positive integers that respectively represent the minimum time in which each person is able to cross the campus if alone; these times are measured in minutes, with each being at most $5000$. (It is a very large campus!)

-----Output-----
Output the minimum possible time it takes to get the entire group from the gate to the dorm.

-----Examples-----
Sample Input 1:
2 15 5
Sample Output 1:
15

Sample Input 2:
4 1 2 7 10
Sample Output 2:
17

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has A cookies, and Aoki has B cookies.
Takahashi will do the following action K times:
 - If Takahashi has one or more cookies, eat one of his cookies.
 - Otherwise, if Aoki has one or more cookies, eat one of Aoki's cookies.
 - If they both have no cookies, do nothing.
In the end, how many cookies will Takahashi and Aoki have, respectively?

-----Constraints-----
 - 0 \leq A \leq 10^{12}
 - 0 \leq B \leq 10^{12}
 - 0 \leq K \leq 10^{12}
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
A B K

-----Output-----
Print the numbers of Takahashi's and Aoki's cookies after K actions.

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

-----Sample Output-----
0 2

Takahashi will do the following:
 - He has two cookies, so he eats one of them.
 - Now he has one cookie left, and he eats it.
 - Now he has no cookies left, but Aoki has three, so Takahashi eats one of them.
Thus, in the end, Takahashi will have 0 cookies, and Aoki will have 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A Russian space traveller Alisa Selezneva, like any other schoolgirl of the late 21 century, is interested in science. She has recently visited the MIT (Moscow Institute of Time), where its chairman and the co-inventor of the time machine academician Petrov told her about the construction of a time machine.

During the demonstration of the time machine performance Alisa noticed that the machine does not have high speed and the girl got interested in the reason for such disadvantage. As it turns out on closer examination, one of the problems that should be solved for the time machine isn't solved by an optimal algorithm. If you find a way to solve this problem optimally, the time machine will run faster and use less energy.

A task that none of the staff can solve optimally is as follows. There exists a matrix a, which is filled by the following rule:

The cells are consecutive positive integers, starting with one. Besides, ai, j < at, k (i, j, t, k ≥ 1), if:

  1. max(i, j) < max(t, k); 
  2. max(i, j) = max(t, k) and j < k; 
  3. max(i, j) = max(t, k), j = k and i > t. 



So, after the first 36 numbers are inserted, matrix a will look as follows:

<image>

To solve the problem, you should learn to find rather quickly for the given values of x1, y1, x2 and y2 (x1 ≤ x2, y1 ≤ y2) the meaning of expression:

<image>

As the meaning of this expression can be large enough, it is sufficient to know only the last 10 digits of the sought value.

So, no one in MTI can solve the given task. Alice was brave enough to use the time machine and travel the past to help you.

Your task is to write a program that uses the given values x1, y1, x2 and y2 finds the last 10 digits of the given expression.

Input

The first input line contains a single integer t (1 ≤ t ≤ 105) — the number of test sets for which you should solve the problem. 

Each of the next t lines contains the description of a test — four positive integers x1, y1, x2 and y2 (1 ≤ x1 ≤ x2 ≤ 109, 1 ≤ y1 ≤ y2 ≤ 109), separated by spaces.

Output

For each query print the meaning of the expression if it contains at most 10 characters. Otherwise, print three characters "." (without the quotes), and then ten last digits of the time expression. Print the answer to each query on a single line. Follow the format, given in the sample as closely as possible.

Examples

Input

5
1 1 1 1
2 2 3 3
2 3 5 6
100 87 288 2002
4 2 5 4


Output

1
24
300
...5679392764
111

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three integers $n, a, b$. Determine if there exists a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$, such that:

There are exactly $a$ integers $i$ with $2 \le i \le n-1$ such that $p_{i-1} < p_i > p_{i+1}$ (in other words, there are exactly $a$ local maximums).

There are exactly $b$ integers $i$ with $2 \le i \le n-1$ such that $p_{i-1} > p_i < p_{i+1}$ (in other words, there are exactly $b$ local minimums).

If such permutations exist, find any such permutation.


-----Input-----

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

The only line of each test case contains three integers $n$, $a$ and $b$ ($2 \leq n \leq 10^5$, $0 \leq a,b \leq n$).

The sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

For each test case, if there is no permutation with the requested properties, output $-1$.

Otherwise, print the permutation that you are found. If there are several such permutations, you may print any of them.


-----Examples-----

Input
3
4 1 1
6 1 2
6 4 0
Output
1 3 2 4
4 2 3 1 5 6
-1


-----Note-----

In the first test case, one example of such permutations is $[1, 3, 2, 4]$. In it $p_1 < p_2 > p_3$, and $2$ is the only such index, and $p_2> p_3 < p_4$, and $3$ the only such index.

One can show that there is no such permutation for the third test case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's define radix sum of number a consisting of digits a_1, … ,a_k and number b consisting of digits b_1, … ,b_k(we add leading zeroes to the shorter number to match longer length) as number s(a,b) consisting of digits (a_1+b_1)mod 10, … ,(a_k+b_k)mod 10. The radix sum of several integers is defined as follows: s(t_1, … ,t_n)=s(t_1,s(t_2, … ,t_n))

You are given an array x_1, … ,x_n. The task is to compute for each integer i (0 ≤ i < n) number of ways to consequently choose one of the integers from the array n times, so that the radix sum of these integers is equal to i. Calculate these values modulo 2^{58}.

Input

The first line contains integer n — the length of the array(1 ≤ n ≤ 100000).

The second line contains n integers x_1, … x_n — array elements(0 ≤ x_i < 100000).

Output

Output n integers y_0, …, y_{n-1} — y_i should be equal to corresponding number of ways modulo 2^{58}.

Examples

Input


2
5 6


Output


1
2


Input


4
5 7 5 7


Output


16
0
64
0

Note

In the first example there exist sequences: sequence (5,5) with radix sum 0, sequence (5,6) with radix sum 1, sequence (6,5) with radix sum 1, sequence (6,6) with radix sum 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Stepan has a very big positive integer.

Let's consider all cyclic shifts of Stepan's integer (if we look at his integer like at a string) which are also integers (i.e. they do not have leading zeros). Let's call such shifts as good shifts. For example, for the integer 10203 the good shifts are the integer itself 10203 and integers 20310 and 31020.

Stepan wants to know the minimum remainder of the division by the given number m among all good shifts. Your task is to determine the minimum remainder of the division by m.


-----Input-----

The first line contains the integer which Stepan has. The length of Stepan's integer is between 2 and 200 000 digits, inclusive. It is guaranteed that Stepan's integer does not contain leading zeros.

The second line contains the integer m (2 ≤ m ≤ 10^8) — the number by which Stepan divides good shifts of his integer.


-----Output-----

Print the minimum remainder which Stepan can get if he divides all good shifts of his integer by the given number m.


-----Examples-----
Input
521
3

Output
2

Input
1001
5

Output
0

Input
5678901234567890123456789
10000

Output
123



-----Note-----

In the first example all good shifts of the integer 521 (good shifts are equal to 521, 215 and 152) has same remainder 2 when dividing by 3.

In the second example there are only two good shifts: the Stepan's integer itself and the shift by one position to the right. The integer itself is 1001 and the remainder after dividing it by 5 equals 1. The shift by one position to the right equals to 1100 and the remainder after dividing it by 5 equals 0, which is the minimum possible remainder.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
More Unsullied army are joining Daenerys Stormborn of the House Targaryen, the First of Her Name, the Unburnt, Queen of Meereen, 
Queen of the Andals and the Rhoynar and the First Men, Khaleesi of the Great Grass Sea, Breaker of Chains, and Mother of Dragons.

We know Grey Worm is the Commander of Unsullied and needs his army organized. He has his unsullied army labelled with random numbers but in sorted order.

Since more army are joining, they come in number. N army come.
Each new Unsullied army have many soldiers each labelled with random numbers but in sorted order. 

Grey Worm has to now merge all army such that they still remain sorted.

Should he fail to do so Daenerys may punish him. He is worried. He needs your help!!

Input:
First line is T. Number of test cases.
For each test case:
First input number N. Number of new Unsullied army joining.
For N number of times, first input 'x' number of soldiers in each Unsullied army followed by 'x' random space separated sorted numbers(Labels of each soldier).

Output:
Print the labels of each soldier of new formed army in sorted order.

Constraints:

1 ≤ T ≤ 100

2 ≤ N ≤ 10

1 ≤ x ≤ 10000

1 ≤ 'label' ≤ 10^6

(Labels need not be unique.)

EXAMPLE:

Input

1

3

4

1 4 7 10

5

3 8 12 16 19

6

2 6 9 14 18 25

Output

1 2 3 4 6 7 8 9 10 12 14 16 18 19 25

SAMPLE INPUT
1
3
4
1 4 7 10
5
3 8 12 16 19
6
2 6 9 14 18 25

SAMPLE OUTPUT
1 2 3 4 6 7 8 9 10 12 14 16 18 19 25

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
At ACME Corp, the seller Robin is selling software like hotcakes. To sell the software, he arranges meetings all over the country. Of course, he always needs to travel there, and sometimes even stay the night. Other times, he decides that a hot dog on the way to a meeting counts as accommodation.

Because Robin is very busy, he hasn’t been able to file his job expenses this month. Eret, the accountant, told him that he could fix it for him, as long as he got the price of all the expenses along with the receipts. Robin did this but misheard him: He has provided a list of all expenses and incomes he has brought in last month, with incomes as positive integers and expenses as negative integers.

Can you help Eret find out how much expenses Robin has paid for the last month?

-----Input-----
The input consist of two lines: One line with the integer $N$, and one line with $N$ integers $k_ i$, representing the numbers Robin has written down.

-----Output-----
Output the sum of all the expenses Robin has paid for the last month.

-----Limits-----
 - $0 \leq N \leq 20000$
 - $-50000 \leq k_ i\leq 500000$ and $k_ i \neq 0$

-----Examples-----
Sample Input 1:
3
1 -2 3
Sample Output 1:
2

Sample Input 2:
5
129 44 394 253 147
Sample Output 2:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Game With Sticks

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
After winning gold and silver in IOI 2014, Akshat and Malvika want to have some fun. Now they are playing a game on a grid made of *n* horizontal and *m* vertical sticks.

An intersection point is any point on the grid which is formed by the intersection of one horizontal stick and one vertical stick.

In the grid shown below, *n*<==<=3 and *m*<==<=3. There are *n*<=+<=*m*<==<=6 sticks in total (horizontal sticks are shown in red and vertical sticks are shown in green). There are *n*·*m*<==<=9 intersection points, numbered from 1 to 9.

The rules of the game are very simple. The players move in turns. Akshat won gold, so he makes the first move. During his/her move, a player must choose any remaining intersection point and remove from the grid all sticks which pass through this point. A player will lose the game if he/she cannot make a move (i.e. there are no intersection points remaining on the grid at his/her move).

Assume that both players play optimally. Who will win the game?

Input Specification:
The first line of input contains two space-separated integers, *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100).

Output Specification:
Print a single line containing "Akshat" or "Malvika" (without the quotes), depending on the winner of the game.

Demo Input:
['2 2\n', '2 3\n', '3 3\n']

Demo Output:
['Malvika\n', 'Malvika\n', 'Akshat\n']

Note:
Explanation of the first sample:

The grid has four intersection points, numbered from 1 to 4.

If Akshat chooses intersection point 1, then he will remove two sticks (1 - 2 and 1 - 3). The resulting grid will look like this.

Now there is only one remaining intersection point (i.e. 4). Malvika must choose it and remove both remaining sticks. After her move the grid will be empty.

In the empty grid, Akshat cannot make any move, hence he will lose.

Since all 4 intersection points of the grid are equivalent, Akshat will lose no matter which one he picks.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera had two bags of potatoes, the first of these bags contains x (x ≥ 1) potatoes, and the second — y (y ≥ 1) potatoes. Valera — very scattered boy, so the first bag of potatoes (it contains x potatoes) Valera lost. Valera remembers that the total amount of potatoes (x + y) in the two bags, firstly, was not gerater than n, and, secondly, was divisible by k.

Help Valera to determine how many potatoes could be in the first bag. Print all such possible numbers in ascending order.


-----Input-----

The first line of input contains three integers y, k, n (1 ≤ y, k, n ≤ 10^9; $\frac{n}{k}$  ≤ 10^5).


-----Output-----

Print the list of whitespace-separated integers — all possible values of x in ascending order. You should print each possible value of x exactly once.

If there are no such values of x print a single integer -1.


-----Examples-----
Input
10 1 10

Output
-1

Input
10 6 40

Output
2 8 14 20 26

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
E: Cut out the sum

problem

Ebi-chan has a sequence (a_1, a_2, ..., a_n). Ebi-chan is worried about the maximum value of the sum of the partial arrays (which may be empty), so please find it. Here, a subarray refers to a continuous subsequence. The sum of empty strings is 0.

In addition, Ebi-chan rewrites this sequence q times, so find this value immediately after each rewrite.

Input format


n q
a_1 a_2 ... a_n
k_1 x_1
...
k_q x_q


Each k_j, x_j (1 \ leq j \ leq q) means rewrite a_ {k_j} to x_j. Note that each rewrite is not independent and the array remains rewritten in subsequent processing.

Constraint

* 1 \ leq n \ leq 10 ^ 5
* 1 \ leq q \ leq 10 ^ 5
* 1 \ leq k_j \ leq n
* | a_i |, | x_j | \ leq 10 ^ 9



Output format

Please output q + 1 line. Output the maximum value of the sum of the subarrays before rewriting on the first line and immediately after the i-th rewrite on the 1 + i line.

Input example 1


5 2
1 2 -3 4 -5
3 3
2 -6


Output example 1


Four
Ten
7


If the subarray (a_l,…, a_r) is represented as a [l, r], the sum of a [1, 4] and a [4, 4] is 4 before rewriting, which is the maximum.

After the first rewrite, the sequence becomes (1, 2, 3, 4, -5), and the maximum sum is 10 of a [1, 4].

After the second rewrite, the sequence becomes (1, -6, 3, 4, -5) and the maximum sum is 7 in a [3, 4].

Input example 2


3 1
-one two Three
1 1


Output example 2


0
1


The sum of the empty strings is 0, which is the maximum before rewriting.





Example

Input

5 2
1 2 -3 4 -5
3 3
2 -6


Output

4
10
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.