vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You may have tried your level best to help Chef but Dr Doof has managed to come up with his masterplan in the meantime. Sadly, you have to help Chef once again. Dr Doof has designed a parenthesis-inator. It throws a stream of $N$ brackets at the target, $1$ bracket per second. The brackets can either be opening or closing. Chef appears in front of the stream at time $t$. If Chef faces an opening bracket, he gets hit. However, if he faces a closing bracket, he may choose to let it pass through him (Chef is immune to closing brackets). Chef gets a chance to counter attack Doof as soon as he finds a balanced non-empty bracket sequence. Help Chef by providing him the minimum time $x$ at which he will be able to launch his counter attack. If Chef is unable to counter attack, answer $-1$.

Formally, you are given a string $S$ of length $N$ consisting only of opening brackets $($ and closing brackets $)$. The substring of $S$ starting at index $L$ and ending at index $R$, i.e. $S_{L} S_{L+1} \ldots S_{R}$ is denoted by $S[L, R]$ . Consider $Q$ cases. In the $i^{\text{th}}$ case, Chef appears at time $t_{i}$ $(1 ≤ t_{i} ≤ N)$ and faces all characters from index $t_{i}$ to $N$. Find the minimum index $x$ $(t_{i} ≤ x ≤ N)$ such that the substring $S[t_{i}, x]$ contains a non-empty balanced bracket subsequence containing the same number of opening brackets as $S[t_{i}, x]$ (i.e., you cannot remove any opening bracket from the substring). If such an $x$ does not exist, print $-1$.

A string $X$ is called a subsequence of a string $Y$ if it is possible to obtain $X$ by erasing some (possibly zero) characters from $Y$ without changing the order of the remaining characters.

A balanced bracket sequence is defined as:  
an empty string is a balanced bracket sequence.
if $s$ is a balanced bracket sequence, then so is $(s)$.
if $s$ and $t$ are balanced bracket sequences, then so is $st$.

$Note :-$ The input files are large. The use of Fast I/O is recommended.

------ Input ------

The first line contains a single integer $T$ denoting the number of testcases.
The first line of each test case contains the string $S$.
The next line contains a single integer $Q$ denoting the number of cases to consider.
The next line contains $Q$ space separated integers, each denoting $t_{i}$.

------ Output ------

For each query, print the minimum value of $x$ in a separate line. If no such $x$ exists, print $-1$.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ |S| ≤ 10^{7}$
$1 ≤ Q ≤ 10^{6}$
$1 ≤ t_{i} ≤ N$
Every character of $S$ is either $($ or $)$.
Sum of $|S|$ and $Q$ over all testcases for a particular test file does not exceed $10^{7}$ and $10^{6}$ respectively.

----- Sample Input 1 ------ 
1
)())((()
3
1 7 6
----- Sample Output 1 ------ 
3
8
-1
----- explanation 1 ------ 
For the first query, Chef chooses to let $S_{1}$ pass through him, gets hit by $S_{2}$ and finally completes a balanced bracket sequence by adding $S_{3}$ to $S_{2}$ at time $x$ = $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's your Birthday. Your colleagues buy you a cake. The numbers of candles on the cake is provided (x). Please note this is not reality, and your age can be anywhere up to 1,000. Yes, you would look a mess.

As a surprise, your colleagues have arranged for your friend to hide inside the cake and burst out. They pretend this is for your benefit, but likely it is just because they want to see you fall over covered in cake. Sounds fun!

When your friend jumps out of the cake, he/she will knock some of the candles to the floor. If the number of candles that fall is higher than 70% of total candles (x), the carpet will catch fire. 

You will work out the number of candles that will fall from the provided string (y). You must add up the character ASCII code of each even indexed (assume a 0 based indexing) character in y, with the alphabetical position of each odd indexed character in y to give the string a total.

example: 'abc' --> a=97, b=2, c=99 --> y total = 198. 

If the carpet catches fire, return 'Fire!', if not, return 'That was close!'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Modern operating system distributions have tools to manage installed software, making it easy to keep the software up-to-date. Putting different pieces of software into ‘packages’ that can be installed separately keeps things simple and avoids duplicate effort and code. But this means that a package may depend on other packages, requiring their installation before that package can be installed. For example, many programs need to use ‘libc,’ which contains standard C-library functions. To keep track of these dependencies, many distributions use some sort of package manager.

When a user wants to install a new package (or set of packages), a package manager takes care of the headache of tracking down which packages are required to install the desired package. Of course, those may also depend on other packages.

For this problem, determine an order (if one exists) that allows a given list of packages to be installed. No package should be installed before all the packages it depends on are installed. You may assume that, at the beginning, no packages have been installed.

-----Input-----
Input consists of up to $10$ test cases. Each test case start with a number $1 \le n \le 1000$, which is the number of packages the user wants to install. This is followed by $n$ lines which describe $n$ packages. Each package description starts with the name of the package and is followed by a space-separated list of the package’s unique dependencies. Each package has at most $20$ dependencies, and each is one of the other $n-1$ packages. Each package name is a string of up to $40$ non-whitespace characters using the English alphabet (a-z, A-Z), digits (0-9), as well as the characters _, -, ., and + (i.e. underscore, minus, period, and plus). Input ends when $n$ is zero.

-----Output-----
For each test case, output the order of package installation that allow them all to be installed after their respective dependencies. If there are multiple possible orderings, then give the ordering that is lexicographically first (using ASCII values for string ordering). If there is some group of packages that are not able to be ordered within the list, output ‘cannot be ordered’ instead of ordering the packages. Put a blank line between each pair of test cases.

-----Examples-----
Sample Input:
14
libattr
vim-X11 vim-common gtk2 libattr
vim-common
gtk2 libtiff atk pango glib2
libtiff zlib libjpeg
atk
pango xorg-x11-libs freetype glib2
glib2
zlib
libjpeg
xorg-x11-libs grep freetype
grep pcre
pcre
freetype
3
emacs xorg-x11 lisp
xorg-x11
lisp emacs
0
Sample Output:
atk
freetype
glib2
libattr
libjpeg
pcre
grep
vim-common
xorg-x11-libs
pango
zlib
libtiff
gtk2
vim-X11

cannot be ordered

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have A 500-yen coins, B 100-yen coins and C 50-yen coins (yen is the currency of Japan).
In how many ways can we select some of these coins so that they are X yen in total?
Coins of the same kind cannot be distinguished. Two ways to select coins are distinguished when, for some kind of coin, the numbers of that coin are different.

-----Constraints-----
 - 0 \leq A, B, C \leq 50
 - A + B + C \geq 1
 - 50 \leq X \leq 20 000
 - A, B and C are integers.
 - X is a multiple of 50.

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

-----Output-----
Print the number of ways to select coins.

-----Sample Input-----
2
2
2
100

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

There are two ways to satisfy the condition:
 - Select zero 500-yen coins, one 100-yen coin and zero 50-yen coins.
 - Select zero 500-yen coins, zero 100-yen coins and two 50-yen coins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have an array with string digits that occurrs more than once, for example, ```arr = ['1', '2', '2', '2', '3', '3']```. How many different string numbers can be generated taking the 6 elements at a time?

We present the list of them below in an unsorted way:
``` 
['223213', '312322', '223312', '222133', '312223', '223321', '223231', '132223', '132322', '223132', '322321', '322312', '231322', '222313', '221233', '213322', '122323', '321322', '221332', '133222', '123232', '323221', '222331', '132232', '321232', '212323', '232213', '232132', '331222', '232312', '332212', '213223', '123322', '322231', '321223', '231232', '233221', '231223', '213232', '312232', '233122', '322132', '223123', '322123', '232231', '323122', '323212', '122233', '212233', '123223', '332221', '122332', '221323', '332122', '232123', '212332', '232321', '322213', '233212', '313222']
``` 
There are ```60``` different numbers and ```122233``` is the lowest one and ```332221``` the highest of all of them.

Given an array, ```arr```, with string digits (from '0' to '9'), you should give the exact amount of different numbers that may be generated with the lowest and highest value but both converted into integer values, using all the digits given in the array for each generated string number.

The function will be called as ```proc_arr()```.
```python
proc_arr(['1', '2', '2', '3', '2', '3']) == [60, 122233, 332221]
```

If the digit '0' is present in the given array will produce string numbers with leading zeroes, that will not be not taken in account when they are converted to integers.
```python
proc_arr(['1','2','3','0','5','1','1','3']) == [3360, 1112335, 53321110]
```
You will never receive an array with only one digit repeated n times.

Features of the random tests:
```
Low performance tests:
Number of tests: 100
Arrays of length between 6 and 10

Higher performance tests:
Number of tests: 100
Arrays of length between 30 and 100
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a function f written in some basic language. The function accepts an integer value, which is immediately written into some variable x. x is an integer variable and can be assigned values from 0 to 2^{32}-1. The function contains three types of commands:

  * for n — for loop; 
  * end — every command between "for n" and corresponding "end" is executed n times; 
  * add — adds 1 to x. 



After the execution of these commands, value of x is returned.

Every "for n" is matched with "end", thus the function is guaranteed to be valid. "for n" can be immediately followed by "end"."add" command can be outside of any for loops.

Notice that "add" commands might overflow the value of x! It means that the value of x becomes greater than 2^{32}-1 after some "add" command. 

Now you run f(0) and wonder if the resulting value of x is correct or some overflow made it incorrect.

If overflow happened then output "OVERFLOW!!!", otherwise print the resulting value of x.

Input

The first line contains a single integer l (1 ≤ l ≤ 10^5) — the number of lines in the function.

Each of the next l lines contains a single command of one of three types:

  * for n (1 ≤ n ≤ 100) — for loop; 
  * end — every command between "for n" and corresponding "end" is executed n times; 
  * add — adds 1 to x. 

Output

If overflow happened during execution of f(0), then output "OVERFLOW!!!", otherwise print the resulting value of x.

Examples

Input


9
add
for 43
end
for 10
for 15
add
end
add
end


Output


161


Input


2
for 62
end


Output


0


Input


11
for 100
for 100
for 100
for 100
for 100
add
end
end
end
end
end


Output


OVERFLOW!!!

Note

In the first example the first "add" is executed 1 time, the second "add" is executed 150 times and the last "add" is executed 10 times. Note that "for n" can be immediately followed by "end" and that "add" can be outside of any for loops.

In the second example there are no commands "add", thus the returning value is 0.

In the third example "add" command is executed too many times, which causes x to go over 2^{32}-1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Miss X has only two combs in her possession, both of which are old and miss a tooth or two. She also has many purses of different length, in which she carries the combs. The only way they fit is horizontally and without overlapping. Given teeth' positions on both combs, find the minimum length of the purse she needs to take them with her.

 It is guaranteed that there is at least one tooth at each end of the comb. 

 - Note, that the combs can not be rotated/reversed.

# Example

 For `comb1 = "*..*" and comb2 = "*.*"`, the output should be `5`

 Although it is possible to place the combs like on the first picture, the best way to do this is either picture 2 or picture 3.

 ![](https://codefightsuserpics.s3.amazonaws.com/tasks/combs/img/cbs.png?_tm=1484930552851)

# Input/Output


 - `[input]` string `comb1`

   A comb is represented as a string. If there is an asterisk ('*') in the ith position, there is a tooth there. Otherwise there is a dot ('.'), which means there is a missing tooth on the comb.

   Constraints: 1 ≤ comb1.length ≤ 10.
   
   

 - `[input]` string `comb2`

   The second comb is represented in the same way as the first one.

   Constraints: 1 ≤ comb2.length ≤ 10.
   

 - `[output]` an integer

   The minimum length of a purse Miss X needs.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alex decided to try his luck in TV shows. He once went to the quiz named "What's That Word?!". After perfectly answering the questions "How is a pseudonym commonly referred to in the Internet?" ("Um... a nick?"), "After which famous inventor we name the unit of the magnetic field strength?" ("Um... Nikola Tesla?") and "Which rock band performs "How You Remind Me"?" ("Um... Nickelback?"), he decided to apply to a little bit more difficult TV show: "What's in This Multiset?!".

The rules of this TV show are as follows: there are n multisets numbered from 1 to n. Each of them is initially empty. Then, q events happen; each of them is in one of the four possible types:

  * 1 x v — set the x-th multiset to a singleton \\{v\}.
  * 2 x y z — set the x-th multiset to a union of the y-th and the z-th multiset. For example: \{1, 3\}∪\{1, 4, 4\}=\{1, 1, 3, 4, 4\}.
  * 3 x y z — set the x-th multiset to a product of the y-th and the z-th multiset. The product A × B of two multisets A, B is defined as \{ \gcd(a, b)  ∣  a ∈ A,  b ∈ B \}, where \gcd(p, q) is the greatest common divisor of p and q. For example: \{2, 2, 3\} × \{1, 4, 6\}=\{1, 2, 2, 1, 2, 2, 1, 1, 3\}.
  * 4 x v — the participant is asked how many times number v occurs in the x-th multiset. As the quiz turned out to be too hard in the past, participants should now give the answers modulo 2 only. 



Note, that x, y and z described above are not necessarily different. In events of types 2 and 3, the sum or the product is computed first, and then the assignment is performed.

Alex is confused by the complicated rules of the show. Can you help him answer the requests of the 4-th type?

Input

The first line contains two integers n and q (1 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^6) — the number of multisets and the number of events.

Each of the following q lines describes next event in the format given in statement. It's guaranteed that 1 ≤ x,y,z ≤ n and 1 ≤ v ≤ 7000 always holds.

It's guaranteed that there will be at least one event of the 4-th type.

Output

Print a string which consists of digits 0 and 1 only, and has length equal to the number of events of the 4-th type. The i-th digit of the string should be equal to the answer for the i-th query of the 4-th type.

Example

Input


4 13
1 1 1
1 2 4
1 3 6
4 4 4
1 4 4
2 2 1 2
2 3 3 4
4 4 4
3 2 2 3
4 2 1
4 2 2
4 2 3
4 2 4


Output


010101

Note

Here is how the multisets look in the example test after each of the events; i is the number of queries processed so far:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
$Neha$  is given a number $N$. She always looks for special thing , this time she is looking for $Special$ $Number$ and $Partial$ $Special$ $Number$. A $Special$ $Number$ is a number whose product of its digits is equal to number itself i.e. $N $, and in this number there is no digit $1$. $Partial$ $Special$ is a number having all the condition same as $Special$ except that it can also have digit $1$ in it .Neha have to count the number of $Special$ and $Partial$ $Special$ $Numbers $for a given  $N$ . She is not so good in programming , so go and help her.

-----Input:-----
- Integers $N$ is taken as input from input stream. 

-----Output:-----
- Print the number of  $Special$ and $Partial$ $Special$ $Numbers $for a given  $N$.

-----Constraints-----
- $1 \leq N \leq 100$ numbers to be count will be less then 10^6

-----Sample Input:-----
3

-----Sample Output:-----
1 20

-----EXPLANATION:-----
There are only one natural numbers, the product of the digits of which is 3  :- {3}.
There are 20 natural numbers with digit 1 , whose  product of the digits  is 3 :-{13, 31, 113 ,131 311 ,1113 ,1131 ,1311, 3111 ,11113, 11131, 11311 ,13111, 31111, 111113, 111131, 111311,113111, 131111 ,311111}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alex enjoys performing magic tricks. He has a trick that requires a deck of n cards. He has m identical decks of n different cards each, which have been mixed together. When Alex wishes to perform the trick, he grabs n cards at random and performs the trick with those. The resulting deck looks like a normal deck, but may have duplicates of some cards.

The trick itself is performed as follows: first Alex allows you to choose a random card from the deck. You memorize the card and put it back in the deck. Then Alex shuffles the deck, and pulls out a card. If the card matches the one you memorized, the trick is successful.

You don't think Alex is a very good magician, and that he just pulls a card randomly from the deck. Determine the probability of the trick being successful if this is the case.

Input

First line of the input consists of two integers n and m (1 ≤ n, m ≤ 1000), separated by space — number of cards in each deck, and number of decks.

Output

On the only line of the output print one floating point number – probability of Alex successfully performing the trick. Relative or absolute error of your answer should not be higher than 10 - 6.

Examples

Input

2 2


Output

0.6666666666666666


Input

4 4


Output

0.4000000000000000


Input

1 2


Output

1.0000000000000000

Note

In the first sample, with probability <image> Alex will perform the trick with two cards with the same value from two different decks. In this case the trick is guaranteed to succeed.

With the remaining <image> probability he took two different cards, and the probability of pulling off the trick is <image>.

The resulting probability is <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array consisting of all integers from $[l, r]$ inclusive. For example, if $l = 2$ and $r = 5$, the array would be $[2, 3, 4, 5]$. What's the minimum number of elements you can delete to make the bitwise AND of the array non-zero?

A bitwise AND is a binary operation that takes two equal-length binary representations and performs the AND operation on each pair of the corresponding bits.


-----Input-----

The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then $t$ cases follow.

The first line of each test case contains two integers $l$ and $r$ ($1 \leq l \leq r \leq 2 \cdot 10^5$) — the description of the array.


-----Output-----

For each test case, output a single integer — the answer to the problem.


-----Examples-----

Input
5
1 2
2 8
4 5
1 5
100000 200000
Output
1
3
0
2
31072


-----Note-----

In the first test case, the array is $[1, 2]$. Currently, the bitwise AND is $0$, as $1\ \& \ 2 = 0$. However, after deleting $1$ (or $2$), the array becomes $[2]$ (or $[1]$), and the bitwise AND becomes $2$ (or $1$). This can be proven to be the optimal, so the answer is $1$.

In the second test case, the array is $[2, 3, 4, 5, 6, 7, 8]$. Currently, the bitwise AND is $0$. However, after deleting $4$, $5$, and $8$, the array becomes $[2, 3, 6, 7]$, and the bitwise AND becomes $2$. This can be proven to be the optimal, so the answer is $3$. Note that there may be other ways to delete $3$ elements.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rachel, being an awesome android programmer, just finished an App that will let us draw a triangle by selecting three points on the touch-plane.Now She asks her friend Bruce to draw a Right-Angled Triangle (we'll call it RAT) by selecting 3 integral points on the plane.
 A RAT is a triangle with Non-Zero area and a right-angle.

But Bruce, being in a hurry as always, makes a mistake on drawing the points. Now Rachel's app can fix Bruce's mistake if only one coordinate of any one point can be adjusted within a distance of 1 units. i.e., if the drawn triangle can be made a RAT by adjusting any one coordinate within 1 unit of distance.

Your task is simple, given 6 coordinates (each Integer pair representing a point), you have to tell can Rachel's app correct Bruce's mistake automatically?

Input:

      First line containing T, the number of test cases.
      Then T lines follow with 6 space separated coordinates.

Output:

      print "YES" in a newline if it's possible.
      otherwise print "NO" in a newline.

Constraints:

      1 ≤ T ≤ 100
      -1000 ≤ xi,yi ≤ 1000

SAMPLE INPUT
3
-1 0 2 0 0 1
2 3 4 5 6 6
0 0 2 0 10 10

SAMPLE OUTPUT
YES
NO
NO

Explanation

Case 1:  For (-1, 0), (2, 0) and (0, 1), shifting (-1, 0) to (0, 0) makes it a RAT. 

Case 2 and Case 3:   No any possible shift results into a RAT.

Note that any point can be moved either in x- or in y- direction at a time by 1 unit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two players play a game.

Initially there are $n$ integers $a_1, a_2, \ldots, a_n$ written on the board. Each turn a player selects one number and erases it from the board. This continues until there is only one number left on the board, i. e. $n - 1$ turns are made. The first player makes the first move, then players alternate turns.

The first player wants to minimize the last number that would be left on the board, while the second player wants to maximize it.

You want to know what number will be left on the board after $n - 1$ turns if both players make optimal moves.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 1000$) — the number of numbers on the board.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$).


-----Output-----

Print one number that will be left on the board.


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

Output
2
Input
3
2 2 2

Output
2


-----Note-----

In the first sample, the first player erases $3$ and the second erases $1$. $2$ is left on the board.

In the second sample, $2$ is left on the board regardless of the actions of the players.

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