vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Santa Claus is the first who came to the Christmas Olympiad, and he is going to be the first to take his place at a desk! In the classroom there are n lanes of m desks each, and there are two working places at each of the desks. The lanes are numbered from 1 to n from the left to the right, the desks in a lane are numbered from 1 to m starting from the blackboard. Note that the lanes go perpendicularly to the blackboard, not along it (see picture).

The organizers numbered all the working places from 1 to 2nm. The places are numbered by lanes (i. e. all the places of the first lane go first, then all the places of the second lane, and so on), in a lane the places are numbered starting from the nearest to the blackboard (i. e. from the first desk in the lane), at each desk, the place on the left is numbered before the place on the right. [Image] The picture illustrates the first and the second samples. 

Santa Clause knows that his place has number k. Help him to determine at which lane at which desk he should sit, and whether his place is on the left or on the right!


-----Input-----

The only line contains three integers n, m and k (1 ≤ n, m ≤ 10 000, 1 ≤ k ≤ 2nm) — the number of lanes, the number of desks in each lane and the number of Santa Claus' place.


-----Output-----

Print two integers: the number of lane r, the number of desk d, and a character s, which stands for the side of the desk Santa Claus. The character s should be "L", if Santa Clause should sit on the left, and "R" if his place is on the right.


-----Examples-----
Input
4 3 9

Output
2 2 L

Input
4 3 24

Output
4 3 R

Input
2 4 4

Output
1 2 R



-----Note-----

The first and the second samples are shown on the picture. The green place corresponds to Santa Claus' place in the first example, the blue place corresponds to Santa Claus' place in the second example.

In the third sample there are two lanes with four desks in each, and Santa Claus has the fourth place. Thus, his place is in the first lane at the second desk on the right.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" would be written "3 4 − 5 +" first subtract 4 from 3, then add 5 to that.

Transform the algebraic expression with brackets into RPN form. 

You can assume that for the test cases below only single letters will be used, brackets [] will not be used and each expression has only one RPN form (no expressions like a*b*c)

----- Sample Input 1 ------ 
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

----- Sample Output 1 ------ 
abc*+
ab+zx+*
at+bac++cd+^*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to decode some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

-----Sample Input:-----
4
1
2
3
4

-----Sample Output:-----
1
12
3
123
45
6
1234
567
89
10

-----EXPLANATION:-----
No need, else pattern can be decode easily.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Sum the Fibonacci

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an array *s* of *n* non-negative integers.

A 5-tuple of integers (*a*,<=*b*,<=*c*,<=*d*,<=*e*) is said to be valid if it satisfies the following conditions: 
 -  1<=≤<=*a*,<=*b*,<=*c*,<=*d*,<=*e*<=≤<=*n* -  (*s**a* | *s**b*) &amp; *s**c* &amp; (*s**d* ^ *s**e*)<==<=2*i* for some integer *i* -  *s**a* &amp; *s**b*<==<=0 
Here, '|' is the bitwise OR, '&amp;' is the bitwise AND and '^' is the bitwise XOR operation.

Find the sum of *f*(*s**a*|*s**b*)<=*<=*f*(*s**c*)<=*<=*f*(*s**d*^*s**e*) over all valid 5-tuples (*a*,<=*b*,<=*c*,<=*d*,<=*e*), where *f*(*i*) is the *i*-th Fibonnaci number (*f*(0)<==<=0,<=*f*(1)<==<=1,<=*f*(*i*)<==<=*f*(*i*<=-<=1)<=+<=*f*(*i*<=-<=2)).

Since answer can be is huge output it modulo 109<=+<=7.

Input Specification:
The first line of input contains an integer *n* (1<=≤<=*n*<=≤<=106).

The second line of input contains *n* integers *s**i* (0<=≤<=*s**i*<=&lt;<=217).

Output Specification:
Output the sum as described above, modulo 109<=+<=7

Demo Input:
['2\n1 2\n', '3\n7 4 1\n', '10\n1 3 0 7 3 7 6 5 7 5\n', '10\n50 9 11 44 39 40 5 39 23 7\n']

Demo Output:
['32\n', '3520\n', '1235424\n', '113860062\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ consecutive seat places in a railway carriage. Each place is either empty or occupied by a passenger.

The university team for the Olympiad consists of $a$ student-programmers and $b$ student-athletes. Determine the largest number of students from all $a+b$ students, which you can put in the railway carriage so that:  no student-programmer is sitting next to the student-programmer;  and no student-athlete is sitting next to the student-athlete. 

In the other words, there should not be two consecutive (adjacent) places where two student-athletes or two student-programmers are sitting.

Consider that initially occupied seat places are occupied by jury members (who obviously are not students at all).


-----Input-----

The first line contain three integers $n$, $a$ and $b$ ($1 \le n \le 2\cdot10^{5}$, $0 \le a, b \le 2\cdot10^{5}$, $a + b > 0$) — total number of seat places in the railway carriage, the number of student-programmers and the number of student-athletes.

The second line contains a string with length $n$, consisting of characters "." and "*". The dot means that the corresponding place is empty. The asterisk means that the corresponding place is occupied by the jury member.


-----Output-----

Print the largest number of students, which you can put in the railway carriage so that no student-programmer is sitting next to a student-programmer and no student-athlete is sitting next to a student-athlete.


-----Examples-----
Input
5 1 1
*...*

Output
2

Input
6 2 3
*...*.

Output
4

Input
11 3 10
.*....**.*.

Output
7

Input
3 2 3
***

Output
0



-----Note-----

In the first example you can put all student, for example, in the following way: *.AB*

In the second example you can put four students, for example, in the following way: *BAB*B

In the third example you can put seven students, for example, in the following way: B*ABAB**A*B

The letter A means a student-programmer, and the letter B — student-athlete.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Student Vladislav came to his programming exam completely unprepared as usual. He got a question about some strange algorithm on a graph — something that will definitely never be useful in real life. He asked a girl sitting next to him to lend him some cheat papers for this questions and found there the following definition:

The minimum spanning tree T of graph G is such a tree that it contains all the vertices of the original graph G, and the sum of the weights of its edges is the minimum possible among all such trees.

Vladislav drew a graph with n vertices and m edges containing no loops and multiple edges. He found one of its minimum spanning trees and then wrote for each edge its weight and whether it is included in the found tree or not. Unfortunately, the piece of paper where the graph was painted is gone and the teacher is getting very angry and demands to see the original graph. Help Vladislav come up with a graph so that the information about the minimum spanning tree remains correct.

Input

The first line of the input contains two integers n and m (<image>) — the number of vertices and the number of edges in the graph.

Each of the next m lines describes an edge of the graph and consists of two integers aj and bj (1 ≤ aj ≤ 109, bj = {0, 1}). The first of these numbers is the weight of the edge and the second number is equal to 1 if this edge was included in the minimum spanning tree found by Vladislav, or 0 if it was not.

It is guaranteed that exactly n - 1 number {bj} are equal to one and exactly m - n + 1 of them are equal to zero.

Output

If Vladislav has made a mistake and such graph doesn't exist, print  - 1.

Otherwise print m lines. On the j-th line print a pair of vertices (uj, vj) (1 ≤ uj, vj ≤ n, uj ≠ vj), that should be connected by the j-th edge. The edges are numbered in the same order as in the input. The graph, determined by these edges, must be connected, contain no loops or multiple edges and its edges with bj = 1 must define the minimum spanning tree. In case there are multiple possible solutions, print any of them.

Examples

Input

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


Output

2 4
1 4
3 4
3 1
3 2


Input

3 3
1 0
2 1
3 1


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n boys and m girls studying in the class. They should stand in a line so that boys and girls alternated there as much as possible. Let's assume that positions in the line are indexed from left to right by numbers from 1 to n + m. Then the number of integers i (1 ≤ i < n + m) such that positions with indexes i and i + 1 contain children of different genders (position i has a girl and position i + 1 has a boy or vice versa) must be as large as possible. 

Help the children and tell them how to form the line.


-----Input-----

The single line of the input contains two integers n and m (1 ≤ n, m ≤ 100), separated by a space.


-----Output-----

Print a line of n + m characters. Print on the i-th position of the line character "B", if the i-th position of your arrangement should have a boy and "G", if it should have a girl. 

Of course, the number of characters "B" should equal n and the number of characters "G" should equal m. If there are multiple optimal solutions, print any of them.


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

Output
GBGBGB

Input
4 2

Output
BGBGBB



-----Note-----

In the first sample another possible answer is BGBGBG. 

In the second sample answer BBGBGB is also optimal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Minister for education is coming! Naturally, nobody wants to perform poorly in front of such a honored guest. However, two hours before the arrival it turned out that one of the classes has a malfunctioning lightbulb — for some reason it doesn't get enough energy. The solution was found quickly: all we've got to do is to change the location of the lightbulb so that it got the maximum amount of energy.

Everybody knows that the power of the lightbulb equals <image>, where C is some constant value and ri is the Euclidean distance from the bulb to the i-th generator. Consequently, our task is to minimize <image>. Of course, we know the positions of all generators.

The bulb should be on the ceiling of the class. The ceiling of the class is in the form of a strictly convex m-gon (the class itself has the form of a right prism with a strictly convex m-gon at the bottom). Help to find the optimum location for the bulb. Assume that all generators are in the plane of the class ceiling. Consider that the plane of the class ceiling has some Cartesian coordinate system introduced.

Input

The first line contains integer n (2 ≤ n ≤ 105) — the number of generators. Each of the next n lines contains a pair of integers xi, yi, representing the coordinates of the i-th generator in the plane of the class ceiling. It's guaranteed that no two generators have the same location.

The next line contains integer m (3 ≤ m ≤ 105) — the number of vertexes in the convex polygon that describes the ceiling of the class. Each of the following m lines contains a pair of integers pi, qi, representing the coordinates of the i-th point of the polygon in the clockwise order. It's guaranteed that the polygon is strictly convex.

The absolute value of all the coordinates don't exceed 106.

Output

Print a single real number — the minimum value of the sum of squares of distances from the generators to the point of the lightbulb's optimal position. The answer will be considered valid if its absolute or relative error doesn't exceed 10 - 4.

Examples

Input

4
3 2
3 4
5 4
5 2
4
3 3
4 4
5 3
4 2


Output

8.00000000

Note

We'll define a strictly convex polygon as a convex polygon with the following property: no three vertices of the polygon lie on the same line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
VK gave a problem to Chef, but Chef is too lazy, so he asked you to solve the problem for him. The statement of the problem follows.
Consider an integer with $N$ digits (in decimal notation, without leading zeroes) $D_1, D_2, D_3, \dots, D_N$. Here, $D_1$ is the most significant digit and $D_N$ the least significant. The weight of this integer is defined as ∑i=2N(Di−Di−1).∑i=2N(Di−Di−1).\sum_{i=2}^N (D_i - D_{i-1})\,.
You are given integers $N$ and $W$. Find the number of positive integers with $N$ digits (without leading zeroes) and weight equal to $W$. Compute this number modulo $10^9+7$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $W$ denoting the number of digits and the required weight.

-----Output-----
For each test case, print a single line containing one integer — the number of $N$-digit positive integers with weight $W$, modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 10^5$
- $2 \le N \le 10^{18}$
- $|W| \le 300$

-----Subtasks-----
Subtask #1 (20 points):
- $1 \le T \le 10^3$
- $2 \le N \le 10^3$
Subtask #2 (80 points): original constraints

-----Example Input-----

1
2 3

-----Example Output-----

6

-----Explanation-----
Example case 1: Remember that the digits are arranged from most significant to least significant as $D_1, D_2$. The two-digit integers with weight $3$ are $14, 25, 36, 47, 58, 69$. For example, the weight of $14$ is $D_2-D_1 = 4-1 = 3$. We can see that there are no other possible numbers.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zonal Computing Olympiad 2012, 26 Nov 2011

We consider sequences of opening and closing brackets with two types of brackets, () and [].  A bracket sequence is well-bracketed if we can pair up each opening bracket with a matching closing bracket in the usual sense.  For instance, the sequences (), [] ([]) and []([]) are well-bracketed, while (, ()], (], )( and [(]) are not well-bracketed.  In the last case, each opening bracket has a matching closing bracket and vice versa, but the intervals spanned by the different types of brackets intersect each other instead of being contained one within the other.

The alternating depth of a well-bracketed sequence tells us the maximum number of times we switch between the two types of brackets when we have inner matched brackets enclosed within outer matched brackets.  For instance, the alternating depth of (), [[[]]] and ()[][] is 1, the alternating depth of [()] and ()([]) is 2, the alternating depth of ([()]) and [()][(([]))] is 3, and so on.

Given a well-bracketed sequence, we are interested in computing three quantities.
- The alternating depth of the sequence.
- The maximum number of symbols between any pair of matched brackets of the type ( and ), including both the outer brackets.
- The maximum number of symbols between any pair of matched brackets of the type [ and ], including both the outer brackets.

For instance, the alternating depth of (([]))[[[()]]] is 2, the maximum number of symbols between a matched pair () is 6 and the maximum number of symbols between a matched pair [] is 8.



-----Input format-----
The input consists of two lines.  The first line is a single integer N, the length of the bracket sequence. Positions in the sequence are numbered 1,2,…,N. The second line is a sequence of N space-separated integers that encode the bracket expression as follows: 1 denotes an opening bracket (, 2 denotes a closing bracket ), 3 denotes an opening bracket [ and 4 denotes a closing bracket ].  Nothing other than 1, 2, 3 or 4 appears in the second line of input and the corresponding expression is guaranteed to be well-bracketed.

-----Output format-----
Your program should print 3 space-separated integers in a line, denoting the three quantities asked for in the following order: alternating depth, length of the maximum sequence between matching () brackets and length of the maximum sequence between matching [] brackets.  

-----Testdata-----
You may assume that 2 ≤ N ≤ 105.  In 30% of the test cases, 2 ≤ N ≤ 103.

- Subtask 1 (30 marks)
- Subtask 2 (70 marks)

-----Sample Input-----
14
1 1 3 4 2 2 3 3 3 1 2 4 4 4

-----Sample Output-----
2 6 8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja and Dima play a game. The rules of the game are very simple. The players have n cards in a row. Each card contains a number, all numbers on the cards are distinct. The players take turns, Sereja moves first. During his turn a player can take one card: either the leftmost card in a row, or the rightmost one. The game ends when there is no more cards. The player who has the maximum sum of numbers on his cards by the end of the game, wins.

Sereja and Dima are being greedy. Each of them chooses the card with the larger number during his move.

Inna is a friend of Sereja and Dima. She knows which strategy the guys are using, so she wants to determine the final score, given the initial state of the game. Help her.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of cards on the table. The second line contains space-separated numbers on the cards from left to right. The numbers on the cards are distinct integers from 1 to 1000.


-----Output-----

On a single line, print two integers. The first number is the number of Sereja's points at the end of the game, the second number is the number of Dima's points at the end of the game.


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

Output
12 5

Input
7
1 2 3 4 5 6 7

Output
16 12



-----Note-----

In the first sample Sereja will take cards with numbers 10 and 2, so Sereja's sum is 12. Dima will take cards with numbers 4 and 1, so Dima's sum is 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tokitsukaze is playing a room escape game designed by SkywalkerT. In this game, she needs to find out hidden clues in the room to reveal a way to escape.

After a while, she realizes that the only way to run away is to open the digital door lock since she accidentally went into a secret compartment and found some clues, which can be interpreted as:

  * Only when you enter n possible different passwords can you open the door; 
  * Passwords must be integers ranged from 0 to (m - 1); 
  * A password cannot be x (0 ≤ x < m) if x and m are not coprime (i.e. x and m have some common divisor greater than 1); 
  * A password cannot be x (0 ≤ x < m) if there exist non-negative integers e and k such that p^e = k m + x, where p is a secret integer; 
  * Any integer that doesn't break the above rules can be a password; 
  * Several integers are hidden in the room, but only one of them can be p. 



Fortunately, she finds that n and m are recorded in the lock. However, what makes Tokitsukaze frustrated is that she doesn't do well in math. Now that she has found an integer that is suspected to be p, she wants you to help her find out n possible passwords, or determine the integer cannot be p.

Input

The only line contains three integers n, m and p (1 ≤ n ≤ 5 × 10^5, 1 ≤ p < m ≤ 10^{18}).

It is guaranteed that m is a positive integer power of a single prime number.

Output

If the number of possible different passwords is less than n, print a single integer -1.

Otherwise, print n distinct integers ranged from 0 to (m - 1) as passwords. You can print these integers in any order. Besides, if there are multiple solutions, print any.

Examples

Input


1 2 1


Output


-1


Input


3 5 1


Output


2 4 3


Input


2 5 4


Output


2 3


Input


4 9 8


Output


2 4 7 5

Note

In the first example, there is no possible password.

In each of the last three examples, the given integer n equals to the number of possible different passwords for the given integers m and p, so if the order of numbers in the output is ignored, the solution is unique as shown above.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your friend has gotten lost in the woods. He has called and asked for you to come get him, but you are very busy and would rather just stay home. You quickly look up a map of the woods. It appears that the woods consist of a small number of clearings, with paths connecting them. You hope that the woods are sufficiently small and simple that your friend can get out easily, even if he is just randomly running around.

From your friend’s description, you can figure out at which clearing he is. Assuming that every time he reaches a clearing, he runs in a uniformly random direction (including back the way he came), and that it takes him exactly one minute to get from clearing to clearing, can you predict how long it will take him to get out on average?

-----Input-----
The first line contains two integers $N$ and $M$, where $N$ is the number of clearings in the woods ($2 \leq N \leq 20$), and $M$ is the total number of paths between clearings. The clearings are numbered $0$ through $N-1$, such that clearing $0$ is the one where your friend is right now and clearing $N-1$ is the exit of the woods.

The next $M$ lines each contain two integers $K$ and $L$, indicating a path between clearing $K$ and clearing $L$ ($0 \leq K, L < N$, $K \neq L$).

You may assume that it is possible for your friend to reach the exit by following paths, that paths do not cross, and that there is at most one path between any two clearings.

-----Output-----
Output a single line containing a single number: the expected value of the number of minutes it will take your friend to get out of the woods.

Your answer may have an absolute error of at most $10^{-5}$.

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

Sample Input 2:
5 6
0 1
0 2
1 2
2 4
0 3
3 4
Sample Output 2:
6.727273

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