vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
For some reason in many American cartoons anvils fall from time to time onto heroes' heads. Of course, safes, wardrobes, cruisers, planes fall sometimes too... But anvils do so most of all.

Anvils come in different sizes and shapes. Quite often they get the hero stuck deep in the ground. But have you ever thought who throws anvils from the sky? From what height? We are sure that such questions have never troubled you!

It turns out that throwing an anvil properly is not an easy task at all. Let's describe one of the most popular anvil throwing models.

Let the height p of the potential victim vary in the range [0;a] and the direction of the wind q vary in the range [ - b;b]. p and q could be any real (floating) numbers. Then we can assume that the anvil will fit the toon's head perfectly only if the following equation has at least one real root: 

<image>

Determine the probability with which an aim can be successfully hit by an anvil.

You can assume that the p and q coefficients are chosen equiprobably and independently in their ranges.

Input

The first line contains integer t (1 ≤ t ≤ 10000) — amount of testcases.

Each of the following t lines contain two space-separated integers a and b (0 ≤ a, b ≤ 106).

Pretests contain all the tests with 0 < a < 10, 0 ≤ b < 10.

Output

Print t lines — the probability of a successful anvil hit for each testcase. The absolute or relative error of the answer should not exceed 10 - 6.

Examples

Input

2
4 2
1 2


Output

0.6250000000
0.5312500000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a permutation P of \{1, 2, \ldots, N\}.
For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R.
Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

-----Constraints-----
 -  2 \le N \le 10^5 
 -  1 \le P_i \le N 
 -  P_i \neq P_j  (i \neq j)
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
P_1 P_2 \ldots P_N

-----Output-----
Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

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

-----Sample Output-----
5

X_{1, 2} = 2, X_{1, 3} = 2, and X_{2, 3} = 1, so the sum is 2 + 2 + 1 = 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tic-Tac-Toe are three cousins. They are playing a game on Fibonacci numbers. The rule of the game is simple -
If the sum of Non-Fibonacci numbers upto N is prime, Tic wins.
If the sum of Non-Fibonacci numbers upto N is even, Tac wins.
If the sum of Non-Fibonacci numbers upto N is odd and not prime, Toe wins.

Fibonacci Numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21 . . . . .

Input: First line of the input contains T, followed by T lines, each containing a number N.

Output: T lines, each containing winners name (Tic, Tac or Toe).

Constraints: 1 ≤ T ≤ 100 | N ≤ 10 ^ 6

SAMPLE INPUT
5
91
12
135
7
66

SAMPLE OUTPUT
Tac
Tic
Tac
Tac
Tic

Explanation

For the 2nd case, N = 12
Fibonacci series till N -> {0,1,1,2,3,5,8}
Sum of Non-Fibonacci numbers upto 12 is -> 4 + 6 + 7 + 9 + 10 + 11 = 47, which is a prime number.
So, Tic wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two teams meet in The Game World Championship. Some scientists consider this game to be the most intellectually challenging game in the world. You are given two strings describing the teams' actions in the final battle. Figure out who became the champion.

Input

The input contains two strings of equal length (between 2 and 20 characters, inclusive). Each line describes the actions of one team.

Output

Output "TEAM 1 WINS" if the first team won, "TEAM 2 WINS" if the second team won, and "TIE" if there was a tie.

Examples

Input

[]()[]8&lt;
8&lt;[]()8&lt;


Output

TEAM 2 WINS


Input

8&lt;8&lt;()
[]8&lt;[]


Output

TIE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Librarian Jurica has $N$ shelves in his library, and each shelf can contain $M$ books. Jurica is a good librarian so he decided to make an inventory in the library and, if it’s necessary, return the books that aren’t in their place to their right place. He moves the books in the following way:
 - moving the books one place to the left or to the right on a shelf if the place to the left or to the right is available,
 - taking a book from a shelf and placing it to an available place on that or any other shelf.

Careful Jurica can’t move books if he has a book in his hands. Additionally, he can’t take more than one book at once.

Jurica has been having back pains ever since he had to move all the volumes of the printed edition of Wikipedia from the first to the second floor so now he wants to put all the books in place with as little lifting as possible because his back is hurting. What is the minimal number of lifting he needs?

-----Input-----
The first line of input contains the integers $N$ and $M$ ($1 \leq N \leq 1000$, $1 \leq M \leq 1000$).

Each of the following $N$ lines contains $M$ integers, the $i$-th line describing the current state of the $i$-th shelf.

Number $0$ denotes an empty place on the shelf, and a number different than $0$ denotes that there is a book in that place denoted with that number. All books are denoted with different numbers from $1$ to $K$, where $K$ is the total number of books on the shelves. After that, an additional $N$ lines follow, each containing $M$ integers, the $i$-th line describing the wanted state of the $i$-th shelf.

In the initial and final state of the shelves, the same books will appear.

-----Output-----
The first and only line of output must contain the required minimal number of lifting or $-1$ if it is impossible to arrange the books in the aforementioned way.

-----Examples-----
Sample Input 1:
2 4
1 0 2 0
3 5 4 0
2 1 0 0
3 0 4 5
Sample Output 1:
2

Sample Input 2:
3 3
1 2 3
4 5 6
7 8 0
4 2 3
6 5 1
0 7 8
Sample Output 2:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During the Steam Summer Sale, Jim's $N-1$ friends have purchased $\mbox{M}$ games, which are numbered from $\mbox{1}$ to $\mbox{M}$. The games are multiplayer. Jim has invited his friends to his basement where they will play by making a LAN-Party. 

Each friend has already decided the game he would like to play for the rest of the day. So there will be a group of friends who will play the same game together.

But then, they face a problem: Currently, none of the friends' PCs are connected. So they have to be connected using the available $\mbox{Q}$ wires. Jim decides to connect friends $u_i$ and $v_i$ with the $\boldsymbol{i}^{th}$ wire one by one. So he starts with wire 1, then with wire 2 and so on. 

A group can start playing their game, only if all the members are connected (if not directly, then there must exist a path connecting them). They want to start playing as soon as possible. 

For each game, find out the wire after adding which the group can start playing. It is also possible that a group will never get connected. In such a case, this group starts crying and you should display -1.

Input Format

On the first line there will be $N$, $\mbox{M}$ and $\mbox{Q}$ each separated by a single space. On the second line we will give you $N$ integers separated by a single space: The $\boldsymbol{i}$-th integer denotes the game friend $\boldsymbol{i}$ wants to play (all between $\mbox{1}$ and $\mbox{M}$). The next $\mbox{Q}$ lines will denote $\mbox{Q}$ wires: $i^{th}$ line denotes $i^{th}$ wire and is denoted by $u_i$ and $v_i$ pairs each separated by a single space. 

Constraints

$1\leq N,M\leq10^5$ For each game $\boldsymbol{i}$, the number of players playing $\boldsymbol{i}$ will be positive. 

$0\leq Q\leq10^5$  

Note
Each game is chosen by at least one player. If a group consists of only one member, then print 0, since this lucky (?) lone player can start right away!

Output Format

Print on the $\boldsymbol{i}^{th} $line the answer for the $\boldsymbol{i}^{th} $game. 

Sample Input
5 2 4
1 2 2 2 1
1 2 
2 3
1 5
4 5 

Sample Output
3
4

Explanation

The group with the game 1 can play after the 3^{rd} wire is added. The group with game 2 can play only after the 4^{th} wire has been added because after adding the 4^{th} wire, a path between (2,3) (3,4) and (2,4) gets created.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A grid of r × c is given.
Numbers from 1 to 8 are written on some squares on the grid.


<image>

It is necessary to connect the squares with numbers and the squares with other numbers with a line.
For the squares with numbers written on them, it is necessary to connect lines with other squares as many as the number written on that square.
However, the lines can be connected only in the vertical and horizontal directions, and up to two lines can be connected in one direction.
<image>

It cannot be connected by a line across other numbers.
<image>

In addition, it is not possible to tie them so that they intersect as follows.
<image>

Since the grid is given as input, please count how many ways there are ways to correctly connect all the squares with numbers.



Input

The input is given in the following format.


r c
grid1
..
..
..
gridr-1


gridi is a string of length c, consisting of numbers from 1 to 8 or ".".

Input meets the following constraints
1 ≤ r, c ≤ 10

Output

Divide the answer value by 100,000,007 and output the remainder on one line

Examples

Input

3 3
.1.
1.1
.1.


Output

0


Input

1 3
1.1


Output

1


Input

3 3
4.2
...
2..


Output

1


Input

7 7
2.3.1.1
.......
2......
.......
..3.3..
.......
2.2.4.3


Output

10

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The official capital and the cultural capital of Berland are connected by a single road running through *n* regions. Each region has a unique climate, so the *i*-th (1<=≤<=*i*<=≤<=*n*) region has a stable temperature of *t**i* degrees in summer.

This summer a group of *m* schoolchildren wants to get from the official capital to the cultural capital to visit museums and sights. The trip organizers transport the children between the cities in buses, but sometimes it is very hot. Specifically, if the bus is driving through the *i*-th region and has *k* schoolchildren, then the temperature inside the bus is *t**i*<=+<=*k* degrees.

Of course, nobody likes it when the bus is hot. So, when the bus drives through the *i*-th region, if it has more than *T**i* degrees inside, each of the schoolchild in the bus demands compensation for the uncomfortable conditions. The compensation is as large as *x**i* rubles and it is charged in each region where the temperature in the bus exceeds the limit.

To save money, the organizers of the trip may arbitrarily add or remove extra buses in the beginning of the trip, and between regions (of course, they need at least one bus to pass any region). The organizers can also arbitrarily sort the children into buses, however, each of buses in the *i*-th region will cost the organizers *cost**i* rubles. Please note that sorting children into buses takes no money.

Your task is to find the minimum number of rubles, which the organizers will have to spend to transport all schoolchildren.

Input Specification:
The first input line contains two integers *n* and *m* (1<=≤<=*n*<=≤<=105; 1<=≤<=*m*<=≤<=106) — the number of regions on the way and the number of schoolchildren in the group, correspondingly. Next *n* lines contain four integers each: the *i*-th line contains *t**i*, *T**i*, *x**i* and *cost**i* (1<=≤<=*t**i*,<=*T**i*,<=*x**i*,<=*cost**i*<=≤<=106). The numbers in the lines are separated by single spaces.

Output Specification:
Print the only integer — the minimum number of roubles the organizers will have to spend to transport all schoolchildren.

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

Demo Input:
['2 10\n30 35 1 100\n20 35 10 10\n', '3 100\n10 30 1000 1\n5 10 1000 3\n10 40 1000 100000\n']

Demo Output:
['120\n', '200065\n']

Note:
In the first sample the organizers will use only one bus to travel through the first region. However, the temperature in the bus will equal 30 + 10 = 40 degrees and each of 10 schoolchildren will ask for compensation. Only one bus will transport the group through the second region too, but the temperature inside won't exceed the limit. Overall, the organizers will spend 100 + 10 + 10 = 120 rubles.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

For a positive, \textbf{even} integer N, we call a pair of arrays A and B to be interesting if they satisfy the following conditions :

|A| = |B| = N/2 i.e. the length of array A is equal to the length of array B.

Each integer from 1 to N occurs exactly once in exactly one of the arrays.

The i^{th} prefix sum of A is not equal to i^{th} prefix sum of B for all 1 ≤ i ≤ N/2-1. Formally, \displaystyle \sum_{j = 1}^{i} A_{j} \neq \sum_{j = 1}^{i} B_{j} for all 1 ≤ i ≤ N/2 - 1

Sum of all elements in A is equal to sum of all elements in B i.e. \displaystyle \sum_{j = 1}^{N/2} A_{j} = \sum_{j = 1}^{N/2} B_{j}

You are given a positive, even integer N. If there exists an interesting pair of arrays, then print "YES" followed by an interesting pair for this given N. If there exists multiple interesting pairs of arrays for given N, you can print any. Print "NO" in a single line if no such pair exists.

------ Input Format ------ 

- First line of input will contain T, the number of test cases. Then the test cases follow.
- Each test case contains a single line of input, the integer N.

------ Output Format ------ 

For each test case, if there exists an interesting pair of arrays, say (A, B), then in the first line print "YES", in the second line print array A separated by spaces, and in third line print array B separated by spaces. Print "NO" in a single line if no such pair exists. If there are multiple answers, print any of them.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$N$ is guaranteed to be even.
- Sum of $N$ over all test cases doesn't exceed $10^{6}$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
2
2
4
----- Sample Output 1 ------ 
NO
YES
1 4
2 3
----- explanation 1 ------ 
Test case 2: Consider $A = [1, 4]$ and $B = [2, 3]$. Every integer from $1$ to $4$ occurs exactly once in exactly one of the arrays. Also, $1$st prefix sum of $A$ is not equal to $1$st prefix sum of $B$ ($1 \neq 2$). And sum of the elements is equal to $5$ for both arrays. So, $(A, B)$ is an interesting pair.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tak performed the following action N times: rolling two dice.
The result of the i-th roll is D_{i,1} and D_{i,2}.
Check if doublets occurred at least three times in a row.
Specifically, check if there exists at lease one i such that D_{i,1}=D_{i,2}, D_{i+1,1}=D_{i+1,2} and D_{i+2,1}=D_{i+2,2} hold.

-----Constraints-----
 - 3 \leq N \leq 100
 - 1\leq D_{i,j} \leq 6
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
D_{1,1} D_{1,2}
\vdots
D_{N,1} D_{N,2}

-----Output-----
Print Yes if doublets occurred at least three times in a row. Print No otherwise.

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

-----Sample Output-----
Yes

From the second roll to the fourth roll, three doublets occurred in a row.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a matrix of size *n*<=×<=*m*. Each element of the matrix is either 1 or 0. You have to determine the number of connected components consisting of 1's. Two cells belong to the same component if they have a common border, and both elements in these cells are 1's.

Note that the memory limit is unusual!

Input Specification:
The first line contains two numbers *n* and *m* (1<=≤<=*n*<=≤<=212, 4<=≤<=*m*<=≤<=214) — the number of rows and columns, respectively. It is guaranteed that *m* is divisible by 4.

Then the representation of matrix follows. Each of *n* next lines contains  one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from 0 to 9 or as uppercase Latin letters from *A* to *F*). Binary representation of each of these numbers denotes next 4 elements of the matrix in the corresponding row. For example, if the number *B* is given, then the corresponding elements are 1011, and if the number is 5, then the corresponding elements are 0101.

Elements are not separated by whitespaces.

Output Specification:
Print the number of connected components consisting of 1's.

Demo Input:
['3 4\n1\nA\n8\n', '2 8\n5F\nE3\n', '1 4\n0\n']

Demo Output:
['3\n', '2\n', '0\n']

Note:
In the first example the matrix is: 

It is clear that it has three components.

The second example: 

It is clear that the number of components is 2.

There are no 1's in the third example, so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Cybermen and the Daleks have long been the Doctor's main enemies. Everyone knows that both these species enjoy destroying everything they encounter. However, a little-known fact about them is that they both also love taking Turing tests!

Heidi designed a series of increasingly difficult tasks for them to spend their time on, which would allow the Doctor enough time to save innocent lives!

The funny part is that these tasks would be very easy for a human to solve.

The first task is as follows. There are some points on the plane. All but one of them are on the boundary of an axis-aligned square (its sides are parallel to the axes). Identify that point.


-----Input-----

The first line contains an integer $n$ ($2 \le n \le 10$).

Each of the following $4n + 1$ lines contains two integers $x_i, y_i$ ($0 \leq x_i, y_i \leq 50$), describing the coordinates of the next point.

It is guaranteed that there are at least $n$ points on each side of the square and all $4n + 1$ points are distinct.


-----Output-----

Print two integers — the coordinates of the point that is not on the boundary of the square.


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

Output
1 1

Input
2
0 0
0 1
0 2
0 3
1 0
1 2
2 0
2 1
2 2

Output
0 3



-----Note-----

In both examples, the square has four sides $x=0$, $x=2$, $y=0$, $y=2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Shooshuns and Sequence 

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day shooshuns found a sequence of *n* integers, written on a blackboard. The shooshuns can perform one operation with it, the operation consists of two steps:
 1.  Find the number that goes *k*-th in the current sequence and add the same number to the end of the sequence; 1.  Delete the first number of the current sequence. 
The shooshuns wonder after how many operations all numbers on the board will be the same and whether all numbers will ever be the same.

Input Specification:
The first line contains two space-separated integers *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=105).

The second line contains *n* space-separated integers: *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=105) — the sequence that the shooshuns found.

Output Specification:
Print the minimum number of operations, required for all numbers on the blackboard to become the same. If it is impossible to achieve, print -1.

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

Demo Output:
['1\n', '-1\n']

Note:
In the first test case after the first operation the blackboard will have sequence [1, 1, 1]. So, one operation is enough to make all numbers the same. Thus, the answer equals one.

In the second test case the sequence will never consist of the same numbers. It will always contain at least two distinct numbers 3 and 1. Thus, the answer equals -1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N of us are going on a trip, by train or taxi.
The train will cost each of us A yen (the currency of Japan).
The taxi will cost us a total of B yen.
How much is our minimum total travel expense?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 20
 - 1 \leq A \leq 50
 - 1 \leq B \leq 50

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

-----Output-----
Print an integer representing the minimum total travel expense.

-----Sample Input-----
4 2 9

-----Sample Output-----
8

The train will cost us 4 \times 2 = 8 yen, and the taxi will cost us 9 yen, so the minimum total travel expense is 8 yen.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You drew lottery N times. In the i-th draw, you got an item of the kind represented by a string S_i.
How many kinds of items did you get?

-----Constraints-----
 - 1 \leq N \leq 2\times 10^5
 - S_i consists of lowercase English letters and has a length between 1 and 10 (inclusive).

-----Input-----
Input is given from Standard Input in the following format:
N
S_1
:
S_N

-----Output-----
Print the number of kinds of items you got.

-----Sample Input-----
3
apple
orange
apple

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

You got two kinds of items: apple and orange.

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:-----
0
01
10
010
101
010
0101
1010
0101
1010

-----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.