vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A valid parentheses sequence is a non-empty string where each character is either '(' or ')', which satisfies the following constraint:

You can find a way to repeat erasing adjacent pairs of parentheses '()' until it becomes empty.

	For example, '(())' and '()((()()))' are valid parentheses sequences, but ')()(' and '(()' are not.

	Mike has a valid parentheses sequence. He really likes everything about his sequence, except the fact that it is quite long. So Mike has recently decided that he will replace his parentheses sequence with a new one in the near future. But not every valid parentheses sequence will satisfy him. To help you understand his requirements we'll introduce the pseudocode of function F(S):

	FUNCTION F( S - a valid parentheses sequence )
	BEGIN
		balance = 0
		max_balance = 0
		FOR index FROM 1 TO LENGTH(S)
		BEGIN
			if S[index] == '(' then balance = balance + 1
			if S[index] == ')' then balance = balance - 1
			max_balance = max( max_balance, balance )
		END
		RETURN max_balance
	END

	In other words, F(S) is equal to the maximal balance over all prefixes of S.

	Let's denote A as Mike's current parentheses sequence, and B as a candidate for a new one. Mike is willing to replace A with B if F(A) is equal to F(B). He would also like to choose B with the minimal possible length amongst ones satisfying the previous condition. If there are several such strings with the minimal possible length, then Mike will choose the least one lexicographically, considering '(' to be less than ')'.

	Help Mike!

-----Input-----

	The first line of the input contains one integer T denoting the number of testcases to process.

	The only line of each testcase contains one string A denoting Mike's parentheses sequence. It is guaranteed that A only consists of the characters '(' and ')'. It is also guaranteed that A is a valid parentheses sequence.

-----Output-----

	The output should contain exactly T lines, one line per each testcase in the order of their appearance. The only line of each testcase should contain one string B denoting the valid parentheses sequence that should be chosen by Mike to replace A.

-----Constraints-----
1 ≤ T ≤ 5;
1 ≤ |A| ≤ 100000(105).

-----Example-----
Input:
1
()((()()))

Output:
((()))

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Amit works at a data recovery company. Every day he is sent broken-down laptops from which he has to recover the hard disk data.

The data to recover is in the form of an array of distinct integers. However, the damaged laptops instead contain many incomplete copies of the original array. The original order of the integers is preserved in all the incomplete arrays, however, elements are missing in unknown positions.

Your job is to create a program for him to reconstruct the original array from these incomplete copies.

If multiple solutions exist, output the lexicographically smallest array. (See the example below)

Input Format
First line contains N, the number of incomplete arrays provided.

2*N lines follow, the first for each contains K, the size of each array and next line contains the array of size K. This array denotes one of the N arrays which has missing values from the original array

Output Format
Print the complete array in a single line.

Constraints
0 ≤ N ≤ 1000

2 ≤ K ≤ 1000

0 ≤ Each integer ≤ 10^6

Note
Any integer will not appear more than once in each array.

This problem was authored by Prinkesh Sharma.

SAMPLE INPUT
2
2
1 3
3
2 3 4

SAMPLE OUTPUT
1 2 3 4

Explanation

There are 2 arrays with some missing values: [1,3] and [2,3,4]. 

Candidates for the original array are [1,2,3,4] and [2,1,3,4]. First one is lexicographically smaller than the second.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write
```python
function repeating_fractions(numerator, denominator)
```
that given two numbers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part has repeated digits, replace those digits with a single digit in parentheses. 

For example:
```python
repeating_fractions(1,1) === '1'
repeating_fractions(1,3) === '0.(3)'
repeating_fractions(2,888) === '0.(0)(2)5(2)5(2)5(2)5(2)5(2)'
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a square-shaped grid with N vertical rows and N horizontal columns. We will denote the square at the i-th row from the top and the j-th column from the left as (i,\ j).

Initially, each square is either white or black. The initial color of the grid is given to you as characters a_{ij}, arranged in a square shape. If the square (i,\ j) is white, a_{ij} is `.`. If it is black, a_{ij} is `#`.

You are developing a robot that repaints the grid. It can repeatedly perform the following operation:

* Select two integers i, j (1 ≤ i,\ j ≤ N). Memorize the colors of the squares (i,\ 1), (i,\ 2), ..., (i,\ N) as c_1, c_2, ..., c_N, respectively. Then, repaint the squares (1,\ j), (2,\ j), ..., (N,\ j) with the colors c_1, c_2, ..., c_N, respectively.



Your objective is to turn all the squares black. Determine whether it is possible, and find the minimum necessary number of operations to achieve it if the answer is positive.

Constraints

* 2 ≤ N ≤ 500
* a_{ij} is either `.` or `#`.

Input

The input is given from Standard Input in the following format:


N
a_{11}...a_{1N}
:
a_{N1}...a_{NN}


Output

If it is possible to turn all the squares black, print the minimum necessary number of operations to achieve the objective. If it is impossible, print `-1` instead.

Examples

Input

2
#.
.#


Output

3


Input

2
.
.#


Output

3


Input

2
..
..


Output

-1


Input

2


Output

0


Input

3
.#.

.#.


Output

2


Input

3
...
.#.
...


Output

5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, find the number of pairs of characters that are same. Pairs (s[i], s[j]), (s[j], s[i]), (s[i], s[i]), (s[j], s[j]) should be considered different.
Example 1:
Input:
S = "air"
Output: 3
Explanation: 3 pairs that are equal:
(S[0], S[0]), (S[1], S[1]) and (S[2], S[2])
Ã¢â¬â¹Example 2:
Input: 
S = "aa"
Output: 4
Explanation: 4 pairs that are equal:
(S[0], S[0]), (S[0], S[1]), (S[1], S[0])
and (S[1], S[1])
Your Task:
You don't need to read input or print anything. Your task is to complete the function equalPairs() which takes the string S as input and returns the number of equal pairs as described in the problem description.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1<=|S|<=10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When Valera was playing football on a stadium, it suddenly began to rain. Valera hid in the corridor under the grandstand not to get wet. However, the desire to play was so great that he decided to train his hitting the ball right in this corridor. Valera went back far enough, put the ball and hit it. The ball bounced off the walls, the ceiling and the floor corridor and finally hit the exit door. As the ball was wet, it left a spot on the door. Now Valera wants to know the coordinates for this spot.

Let's describe the event more formally. The ball will be considered a point in space. The door of the corridor will be considered a rectangle located on plane xOz, such that the lower left corner of the door is located at point (0, 0, 0), and the upper right corner is located at point (a, 0, b) . The corridor will be considered as a rectangular parallelepiped, infinite in the direction of increasing coordinates of y. In this corridor the floor will be considered as plane xOy, and the ceiling as plane, parallel to xOy and passing through point (a, 0, b). We will also assume that one of the walls is plane yOz, and the other wall is plane, parallel to yOz and passing through point (a, 0, b).

We'll say that the ball hit the door when its coordinate y was equal to 0. Thus the coordinates of the spot are point (x0, 0, z0), where 0 ≤ x0 ≤ a, 0 ≤ z0 ≤ b. To hit the ball, Valera steps away from the door at distance m and puts the ball in the center of the corridor at point <image>. After the hit the ball flies at speed (vx, vy, vz). This means that if the ball has coordinates (x, y, z), then after one second it will have coordinates (x + vx, y + vy, z + vz).

See image in notes for clarification.

When the ball collides with the ceiling, the floor or a wall of the corridor, it bounces off in accordance with the laws of reflection (the angle of incidence equals the angle of reflection). In the problem we consider the ideal physical model, so we can assume that there is no air resistance, friction force, or any loss of energy.

Input

The first line contains three space-separated integers a, b, m (1 ≤ a, b, m ≤ 100). The first two integers specify point (a, 0, b), through which the ceiling and one of the corridor walls pass. The third integer is the distance at which Valera went away from the door.

The second line has three space-separated integers vx, vy, vz (|vx|, |vy|, |vz| ≤ 100, vy < 0, vz ≥ 0) — the speed of the ball after the hit.

It is guaranteed that the ball hits the door.

Output

Print two real numbers x0, z0 — the x and z coordinates of point (x0, 0, z0), at which the ball hits the exit door. The answer will be considered correct, if its absolute or relative error does not exceed 10  - 6.

Examples

Input

7 2 11
3 -11 2


Output

6.5000000000 2.0000000000


Input

7 2 11
4 -3 3


Output

4.1666666667 1.0000000000

Note

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It seems like the year of 2013 came only yesterday. Do you know a curious fact? The year of 2013 is the first year after the old 1987 with only distinct digits.

Now you are suggested to solve the following problem: given a year number, find the minimum year number which is strictly larger than the given one and has only distinct digits.


-----Input-----

The single line contains integer y (1000 ≤ y ≤ 9000) — the year number.


-----Output-----

Print a single integer — the minimum year number that is strictly larger than y and all it's digits are distinct. It is guaranteed that the answer exists.


-----Examples-----
Input
1987

Output
2013

Input
2013

Output
2014

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a 4x4 grid. You play a game — there is a sequence of tiles, each of them is either 2x1 or 1x2. Your task is to consequently place all tiles from the given sequence in the grid. When tile is placed, each cell which is located in fully occupied row or column is deleted (cells are deleted at the same time independently). You can place tile in the grid at any position, the only condition is that tiles (and tile parts) should not overlap. Your goal is to proceed all given figures and avoid crossing at any time.

Input

The only line contains a string s consisting of zeroes and ones (1 ≤ |s| ≤ 1000). Zero describes vertical tile, one describes horizontal tile.

Output

Output |s| lines — for each tile you should output two positive integers r,c, not exceeding 4, representing numbers of smallest row and column intersecting with it.

If there exist multiple solutions, print any of them.

Example

Input


010


Output


1 1
1 2
1 4

Note

Following image illustrates the example after placing all three tiles: 

<image> Then the first row is deleted:  <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Robot Doc is located in the hall, with n computers stand in a line, numbered from left to right from 1 to n. Each computer contains exactly one piece of information, each of which Doc wants to get eventually. The computers are equipped with a security system, so to crack the i-th of them, the robot needs to collect at least a_{i} any pieces of information from the other computers. Doc can hack the computer only if he is right next to it.

The robot is assembled using modern technologies and can move along the line of computers in either of the two possible directions, but the change of direction requires a large amount of resources from Doc. Tell the minimum number of changes of direction, which the robot will have to make to collect all n parts of information if initially it is next to computer with number 1.

It is guaranteed that there exists at least one sequence of the robot's actions, which leads to the collection of all information. Initially Doc doesn't have any pieces of information.


-----Input-----

The first line contains number n (1 ≤ n ≤ 1000). The second line contains n non-negative integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} < n), separated by a space. It is guaranteed that there exists a way for robot to collect all pieces of the information.


-----Output-----

Print a single number — the minimum number of changes in direction that the robot will have to make in order to collect all n parts of information.


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

Output
1

Input
5
4 2 3 0 1

Output
3

Input
7
0 3 1 0 5 2 6

Output
2



-----Note-----

In the first sample you can assemble all the pieces of information in the optimal manner by assembling first the piece of information in the first computer, then in the third one, then change direction and move to the second one, and then, having 2 pieces of information, collect the last piece.

In the second sample to collect all the pieces of information in the optimal manner, Doc can go to the fourth computer and get the piece of information, then go to the fifth computer with one piece and get another one, then go to the second computer in the same manner, then to the third one and finally, to the first one. Changes of direction will take place before moving from the fifth to the second computer, then from the second to the third computer, then from the third to the first computer.

In the third sample the optimal order of collecting parts from computers can look like that: 1->3->4->6->2->5->7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer array A, and an integer target, return the number of tuples i, j, k  such that i < j < k and A[i] + A[j] + A[k] == target.
As the answer can be very large, return it modulo 109 + 7.
 
Example 1:
Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:
Input: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

 
Constraints:

3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ram has invented a magic sequence. Each element of the sequence is defined by the same recursive definition - take some linear combination of previous elements (whose coefficients are fixed) and add to them the n-th powers of some integers. Formally: Xn = Xn-1*a1 + ... + Xn-i*ai + b1*d1^n + ... + bj*dj^n, for some integer constants p,q,a1,...,ap,b1,..., bq,d1,..., dq. Of course, as the values can quickly grow, he computed them modulo a fixed value: 10^6. He wrote many consecutive values of the sequence, but then he lost most of his work. All he has now, is 10 consecutive values taken from somewhere in the sequence (he doesn't know at what n they begin), and the recursive rule. And he would like to recover the sequence, or at the very least, to be able to write the next 10 values taken from the sequence.

-----Input-----
First, two integers, 0<=p<=4, 0<=q<=4. Then come the descriptions of the coefficients, -100 <= a1,...,ap,b1,..., bq,d1,..., dq <= 100. Then, the following 10 integers are Xn,X(n+1),...,X(n+9) for some unknown n.

-----Output-----
10 integers - X(n+10),X(n+11),...,X(n+19)

-----Example-----
Input:

1 1

1

1

1

11 12 13 14 15 16 17 18 19 20

Output:

21 22 23 24 25 26 27 28 29 30

Input:

1 1

1

1

2

1 3 7 15 31 63 127 255 511 1023



Output:

2047 4095 8191 16383 32767 65535 131071 262143 524287 48575

Input:

2 0

1 1

1 1 2 3 5 8 13 21 34 55


Output:

89 144 233 377 610 987 1597 2584 4181 6765

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Transformation: from A to B

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasily has a number *a*, which he wants to turn into a number *b*. For this purpose, he can do two types of operations:
 -  multiply the current number by 2 (that is, replace the number *x* by 2·*x*); -  append the digit 1 to the right of current number (that is, replace the number *x* by 10·*x*<=+<=1). 
You need to help Vasily to transform the number *a* into the number *b* using only the operations described above, or find that it is impossible.

Note that in this task you are not required to minimize the number of operations. It suffices to find any way to transform *a* into *b*.

Input Specification:
The first line contains two positive integers *a* and *b* (1<=≤<=*a*<=&lt;<=*b*<=≤<=109) — the number which Vasily has and the number he wants to have.

Output Specification:
If there is no way to get *b* from *a*, print "NO" (without quotes).

Otherwise print three lines. On the first line print "YES" (without quotes). The second line should contain single integer *k* — the length of the transformation sequence. On the third line print the sequence of transformations *x*1,<=*x*2,<=...,<=*x**k*, where:
 -  *x*1 should be equal to *a*, -  *x**k* should be equal to *b*, -  *x**i* should be obtained from *x**i*<=-<=1 using any of two described operations (1<=&lt;<=*i*<=≤<=*k*). 
If there are multiple answers, print any of them.

Demo Input:
['2 162\n', '4 42\n', '100 40021\n']

Demo Output:
['YES\n5\n2 4 8 81 162 \n', 'NO\n', 'YES\n5\n100 200 2001 4002 40021 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are three horses living in a horse land: one gray, one white and one gray-and-white. The horses are really amusing animals, which is why they adore special cards. Each of those cards must contain two integers, the first one on top, the second one in the bottom of the card. Let's denote a card with a on the top and b in the bottom as (a, b).

Each of the three horses can paint the special cards. If you show an (a, b) card to the gray horse, then the horse can paint a new (a + 1, b + 1) card. If you show an (a, b) card, such that a and b are even integers, to the white horse, then the horse can paint a new $(\frac{a}{2}, \frac{b}{2})$ card. If you show two cards (a, b) and (b, c) to the gray-and-white horse, then he can paint a new (a, c) card.

Polycarpus really wants to get n special cards (1, a_1), (1, a_2), ..., (1, a_{n}). For that he is going to the horse land. He can take exactly one (x, y) card to the horse land, such that 1 ≤ x < y ≤ m. How many ways are there to choose the card so that he can perform some actions in the horse land and get the required cards?

Polycarpus can get cards from the horses only as a result of the actions that are described above. Polycarpus is allowed to get additional cards besides the cards that he requires.


-----Input-----

The first line contains two integers n, m (1 ≤ n ≤ 10^5, 2 ≤ m ≤ 10^9). The second line contains the sequence of integers a_1, a_2, ..., a_{n} (2 ≤ a_{i} ≤ 10^9). Note, that the numbers in the sequence can coincide.

The numbers in the lines are separated by single spaces.


-----Output-----

Print a single integer — the answer to the problem. 

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


-----Examples-----
Input
1 6
2

Output
11

Input
1 6
7

Output
14

Input
2 10
13 7

Output
36

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s, return the maximum number of unique substrings that the given string can be split into.
You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.
A substring is a contiguous sequence of characters within a string.
 
Example 1:
Input: s = "ababccc"
Output: 5
Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.

Example 2:
Input: s = "aba"
Output: 2
Explanation: One way to split maximally is ['a', 'ba'].

Example 3:
Input: s = "aa"
Output: 1
Explanation: It is impossible to split the string any further.

 
Constraints:


1 <= s.length <= 16


s contains only lower case English letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya and Vasya are playing a game. Petya's got n non-transparent glasses, standing in a row. The glasses' positions are indexed with integers from 1 to n from left to right. Note that the positions are indexed but the glasses are not.

First Petya puts a marble under the glass in position s. Then he performs some (possibly zero) shuffling operations. One shuffling operation means moving the glass from the first position to position p_1, the glass from the second position to position p_2 and so on. That is, a glass goes from position i to position p_{i}. Consider all glasses are moving simultaneously during one shuffling operation. When the glasses are shuffled, the marble doesn't travel from one glass to another: it moves together with the glass it was initially been put in.

After all shuffling operations Petya shows Vasya that the ball has moved to position t. Vasya's task is to say what minimum number of shuffling operations Petya has performed or determine that Petya has made a mistake and the marble could not have got from position s to position t.


-----Input-----

The first line contains three integers: n, s, t (1 ≤ n ≤ 10^5; 1 ≤ s, t ≤ n) — the number of glasses, the ball's initial and final position. The second line contains n space-separated integers: p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n) — the shuffling operation parameters. It is guaranteed that all p_{i}'s are distinct.

Note that s can equal t.


-----Output-----

If the marble can move from position s to position t, then print on a single line a non-negative integer — the minimum number of shuffling operations, needed to get the marble to position t. If it is impossible, print number -1.


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

Output
3

Input
4 3 3
4 1 3 2

Output
0

Input
4 3 4
1 2 3 4

Output
-1

Input
3 1 3
2 1 3

Output
-1

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