vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
# Let's watch a parade!
## Brief
You're going to watch a parade, but you only care about one of the groups marching. The parade passes through the street where your house is. Your house is at number `location` of the street. Write a function `parade_time` that will tell you the times when you need to appear to see all appearences of that group.

## Specifications
You'll be given:

* A `list` of `string`s containing `groups` in the parade, in order of appearance. A group may appear multiple times. You want to see all the parts of your favorite group.
* An positive `integer` with the `location` on the parade route where you'll be watching.
* An positive `integer` with the `speed` of the parade
* A `string` with the `pref`ferred group you'd like to see

You need to return the time(s) you need to be at the parade to see your favorite group as a `list` of `integer`s.

It's possible the group won't be at your `location` at an exact `time`. In that case, just be sure to get there right before it passes (i.e. the largest integer `time` before the float passes the `position`).

## Example
```python
groups = ['A','B','C','D','E','F']
location = 3
speed = 2
pref = 'C'
                  v
Locations: |0|1|2|3|4|5|6|7|8|9|...
F E D C B A      | |               time = 0
> > F E D C B A  | |               time = 1
    > > F E D C B|A|               time = 2
        > > F E D|C|B A            time = 3
                  ^
parade_time(['A','B','C','D','E','F'], 3, 2,'C']) == [3]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pussycat Sonya is standing on the graph in the node with number 1 and she wants to reach the node number N. It's known that graph consists of N nodes and M undirected edges. Getting through the edge takes 1 unit of time. It's also known that there are K moments of time in which some edges will disappear. Let's consider this process in more detail. Sonya stands in the node number 1 at the moment of time = 0. Moving to any of adjacent nodes through the edge increases time by 1 unit. And once she changed her location all edges that must disappear at that moment of time become unavailable.

What is the minimal time Sonya needs to reach the node  number N? If it's impossible print -1.

Input:
The first line of input contains three integers N - the number of nodes, M - the number of edges and K - the number of moments of time in which some edges will disappear.
Each of the next M lines contains a pair of integers Ui and Vi which means  that edge number i connects node number Ui and node number Vi. You can assume that between any pair of nodes there's no more than one connecting edge and there's no edge connecting some node to itself.
Then K lines follow. Each of these lines contains a pair of integers T and X which means that at moment of time T the edge number X will disappear. You can assume that all Xs will be unique.

Output:
Print the minimal time Sonya needs to reach the node  number N, if it's impossible print -1.

Constraints:
1 ≤ N ≤ 10^5
0 ≤ K ≤ M ≤ min((N · (N - 1)) / 2, 10^5)
1 ≤ Ui, Vi ≤ N
1 ≤ T ≤ 10^9
1 ≤ X ≤ M

SAMPLE INPUT
5 5 1
1 2
1 3
2 5
3 4
4 5
1 3

SAMPLE OUTPUT
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string s = s_1s_2... s_{n} (n is the length of the string), consisting only of characters "." and "#" and m queries. Each query is described by a pair of integers l_{i}, r_{i} (1 ≤ l_{i} < r_{i} ≤ n). The answer to the query l_{i}, r_{i} is the number of such integers i (l_{i} ≤ i < r_{i}), that s_{i} = s_{i} + 1.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.


-----Input-----

The first line contains string s of length n (2 ≤ n ≤ 10^5). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer m (1 ≤ m ≤ 10^5) — the number of queries. Each of the next m lines contains the description of the corresponding query. The i-th line contains integers l_{i}, r_{i} (1 ≤ l_{i} < r_{i} ≤ n).


-----Output-----

Print m integers — the answers to the queries in the order in which they are given in the input.


-----Examples-----
Input
......
4
3 4
2 3
1 6
2 6

Output
1
1
5
4

Input
#..###
5
1 3
5 6
1 5
3 6
3 4

Output
1
1
2
2
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Remove the parentheses
=
In this kata you are given a string for example:

```python
"example(unwanted thing)example"
```

Your task is to remove everything inside the parentheses as well as the parentheses themselves.

The example above would return:

```python
"exampleexample"
```

Other than parentheses only letters and spaces can occur in the string. Don't worry about other brackets like ```"[]"``` and ```"{}"``` as these will never appear.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Professor Bajtocy is conducting experiments on alien DNA. He has discovered that it is subject to repetitive mutations — each mutation happens in the same way: some continuous subsequence of the alien DNA becomes active, copies itself, the copy gets mangled and inserts itself right after the original subsequence. The mangled copy of the activated continuous subsequence is formed by first joining all the elements at the even positions in that subsequence, and then joining all the elements at the odd ones at the end. That is, if the activated subsequence consists of 11 elements and represented as s1s2... s11, its mangled copy is s2s4s6s8s10s1s3s5s7s9s11.

For example, if the original sequence was "ACTGG" and the mutation happened on the segment [2, 4] (that is the activated subsequence is "CTG"), the mutated DNA is: "ACTGTCGG". The mangled copy of the activated subsequence is marked with bold font.

Professor Bajtocy has written down the original DNA sequence and the mutations that sequentially happened to it, and he now asks you to recover the first k elements of the DNA sequence after all the mutations.

Input

The first line of input contains the original DNA sequence, consisting only of letters "A", "C", "T" and "G" and not exceeding 3·106 in length. 

The second line contains a single integer k (1 ≤ k ≤ 3·106).

The third line contains a single integer n (0 ≤ n ≤ 5000) — the number of mutations. The next n lines describe the mutations in chronological order — each mutation is described by two numbers li and ri (1 ≤ li ≤ ri ≤ 109), meaning that the continuous subsequence [li, ri] has become active and cloned itself, joining itself with the mangled copy. 

It is guaranteed that the input data is correct, that is, no mutation acts on non-existing elements of the DNA sequence, and the resulting DNA sequence has at least k elements.

Assume that the DNA elements are indexed starting from 1 and that the notation [l, r] meaning the continuous subsequence of DNA sequence that consists of r - l + 1 elements starting at the l-th DNA sequence element and ending at the r-th DNA sequence element.

Output

Output a single line, containing the first k letters of the mutated DNA sequence.

Examples

Input

GAGA
4
0


Output

GAGA


Input

ACGTACGT
16
2
1 2
2 8


Output

ACCAGTACCGACATCG

Note

In the second example, after the first mutation the sequence is "ACCAGTACGT". After the second mutation it's "ACCAGTACCGACATCGT".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Calculate the sum of all the multiples of 3 or 7 below the natural number N.
Example 1:
Input: 10
Output: 25
Explanation:
Numbers that are multiple of 3 or 7
are 3, 6, 7, 9 so sum will be 25.
Example 2:
Input: 25
Output: 84
Explanation: 
Numbers that are multiple of 3 or 7
are 3, 6, 7, 9, 12, 14, 15, 18 so 
sum will be 84.
Your Task:
You don't need to read or print anything. Your task is to complete the function sum() which takes N as input parameter and returns the sum of numbers that are multiple of 3 or 7.
Expected Time Complexity: O(1)
Expected Space Complexity: O(1)
Constraints:
1 <= N <= 1000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two positive integers n and k. Print the k-th positive integer that is not divisible by n.

For example, if n=3, and k=7, then all numbers that are not divisible by 3 are: 1, 2, 4, 5, 7, 8, 10, 11, 13 .... The 7-th number among them is 10.

Input

The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases in the input. Next, t test cases are given, one per line.

Each test case is two positive integers n (2 ≤ n ≤ 10^9) and k (1 ≤ k ≤ 10^9).

Output

For each test case print the k-th positive integer that is not divisible by n.

Example

Input


6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1


Output


10
15
1999999999
113
1000000001
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A message containing letters from A-Z is being encoded to numbers using the following mapping:


'A' -> 1
'B' -> 2
...
'Z' -> 26


Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:


Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).


Example 2:


Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a positive integer $x$. Multiply its nonzero digits and you get another integer $y$. Repeating this process, you eventually arrive at a single digit between $1$ and $9$. Write a program that reads $x$ and outputs the resulting digit.

-----Input-----
An integer $x$ with $10 \leq x \leq 1000$.

-----Output-----
Print a digit between $1$ and $9$, the result of repeatedly multiplying the nonzero digits of $x$ as described above.

-----Explanation of Sample Inputs-----
In Sample Input $1$, we have $x = 808$. Multiplying $8$ and $8$, we arrive at $64$. Then we get $6 \cdot 4 = 24$, and finally $2 \cdot 4 = 8$, which is the sample output.

In Sample Input $2$, there is only a single nonzero digit, $2$. The product of all digits in a set containing only a single element is the digit itself. Thus the answer is $2$.

-----Examples-----
Sample Input:
808
Sample Output:
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a system of n vessels arranged one above the other as shown in the figure below. Assume that the vessels are numbered from 1 to n, in the order from the highest to the lowest, the volume of the i-th vessel is a_{i} liters. [Image] 

Initially, all the vessels are empty. In some vessels water is poured. All the water that overflows from the i-th vessel goes to the (i + 1)-th one. The liquid that overflows from the n-th vessel spills on the floor.

Your task is to simulate pouring water into the vessels. To do this, you will need to handle two types of queries:  Add x_{i} liters of water to the p_{i}-th vessel;  Print the number of liters of water in the k_{i}-th vessel. 

When you reply to the second request you can assume that all the water poured up to this point, has already overflown between the vessels.


-----Input-----

The first line contains integer n — the number of vessels (1 ≤ n ≤ 2·10^5). The second line contains n integers a_1, a_2, ..., a_{n} — the vessels' capacities (1 ≤ a_{i} ≤ 10^9). The vessels' capacities do not necessarily increase from the top vessels to the bottom ones (see the second sample). The third line contains integer m — the number of queries (1 ≤ m ≤ 2·10^5). Each of the next m lines contains the description of one query. The query of the first type is represented as "1 p_{i} x_{i}", the query of the second type is represented as "2 k_{i}" (1 ≤ p_{i} ≤ n, 1 ≤ x_{i} ≤ 10^9, 1 ≤ k_{i} ≤ n).


-----Output-----

For each query, print on a single line the number of liters of water in the corresponding vessel.


-----Examples-----
Input
2
5 10
6
1 1 4
2 1
1 2 5
1 1 4
2 1
2 2

Output
4
5
8

Input
3
5 10 8
6
1 1 12
2 2
1 1 6
1 3 2
2 2
2 3

Output
7
10
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zeyad wants to commit n crimes in Egypt and not be punished at the end. There are several types of crimes. For example, bribery is a crime but is not considered such when repeated twice. Therefore, bribery is not considered a crime when repeated an even number of times. Speeding is a crime, but is not considered such when repeated a number of times which is a multiple of five.

More specifically, c conditions on crime repetitions are known. Each condition describes the crime type ti and its multiplicity mi. If the number of times Zeyad committed the crime ti is a multiple of mi, Zeyad will not be punished for crime ti. Some crimes may be listed more than once. In this case fulfilling at least one condition for this crime is enough to not be punished for it. Of course, if for certain crime the number of times Zeyad committed it is zero, he is innocent with respect to this crime.

Now Zeyad is interested in a number of ways he can commit exactly n crimes without any punishment.

The order of commiting the crimes matters. More formally, two ways, sequences w1 and w2, of committing n crimes are equal if w1i = w2i, for all 1 ≤ i ≤ n.

Input

The first line contains two integers n and c (0 ≤ n ≤ 1018, 0 ≤ c ≤ 1000) — the number of crimes Zeyad would like to commit and the number of conditions he is aware of.

Then the definitions for c conditions follow. There are 26 types of crimes. Each crime definition consists of crime type — a capital Latin letter — and its multiplicity. 

The multiplicity of each crime is a positive integer number and the product of all multiplicities does not exceed 123. Some conditions may be repeated in the input more than once.

Crime of multiplicity 1 is not yielding any punishment regardless of the number of times it was committed. The strictness of the law is compensated by the fact that it's non-mandatory.

Obviously, if some crime is not listed in the set of conditions, then Zeyad will not consider it, as committing it would unavoidably lead to the punishment.

Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin stream (you may also use the %I64d specificator).

Output

Output the number of different ways Zeyad can commit exactly n crimes with no punishment modulo 12345.

Examples

Input

5 2
A 1
B 2


Output

16


Input

6 3
A 1
B 2
C 3


Output

113


Input

8 3
A 2
A 3
B 2


Output

128

Note

In the first test case, the 16 ways are: AAAAA, AAABB, AABAB, AABBA, ABAAB, ABABA, ABBAA, BAAAB, BAABA, BABAA, BBAAA, ABBBB, BABBB, BBABB, BBBAB, BBBBA.

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

Walking through the streets of Marshmallow City, Slastyona have spotted some merchants selling a kind of useless toy which is very popular nowadays – caramel spinner! Wanting to join the craze, she has immediately bought the strange contraption.

Spinners in Sweetland have the form of V-shaped pieces of caramel. Each spinner can, well, spin around an invisible magic axis. At a specific point in time, a spinner can take 4 positions shown below (each one rotated 90 degrees relative to the previous, with the fourth one followed by the first one):

 [Image] 

After the spinner was spun, it starts its rotation, which is described by a following algorithm: the spinner maintains its position for a second then majestically switches to the next position in clockwise or counter-clockwise order, depending on the direction the spinner was spun in.

Slastyona managed to have spinner rotating for exactly n seconds. Being fascinated by elegance of the process, she completely forgot the direction the spinner was spun in! Lucky for her, she managed to recall the starting position, and wants to deduct the direction given the information she knows. Help her do this.


-----Input-----

There are two characters in the first string – the starting and the ending position of a spinner. The position is encoded with one of the following characters: v (ASCII code 118, lowercase v), < (ASCII code 60), ^ (ASCII code 94) or > (ASCII code 62) (see the picture above for reference). Characters are separated by a single space.

In the second strings, a single number n is given (0 ≤ n ≤ 10^9) – the duration of the rotation.

It is guaranteed that the ending position of a spinner is a result of a n second spin in any of the directions, assuming the given starting position.


-----Output-----

Output cw, if the direction is clockwise, ccw – if counter-clockwise, and undefined otherwise.


-----Examples-----
Input
^ >
1

Output
cw

Input
< ^
3

Output
ccw

Input
^ v
6

Output
undefined

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S consisting of lowercase English letters.
Find the lexicographically (alphabetically) smallest lowercase English letter that does not occur in S.
If every lowercase English letter occurs in S, print None instead.

-----Constraints-----
 - 1 \leq |S| \leq 10^5 (|S| is the length of string S.)
 - S consists of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the lexicographically smallest lowercase English letter that does not occur in S.
If every lowercase English letter occurs in S, print None instead.

-----Sample Input-----
atcoderregularcontest

-----Sample Output-----
b

The string atcoderregularcontest contains a, but does not contain b.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kirito is stuck on a level of the MMORPG he is playing now. To move on in the game, he's got to defeat all *n* dragons that live on this level. Kirito and the dragons have strength, which is represented by an integer. In the duel between two opponents the duel's outcome is determined by their strength. Initially, Kirito's strength equals *s*.

If Kirito starts duelling with the *i*-th (1<=≤<=*i*<=≤<=*n*) dragon and Kirito's strength is not greater than the dragon's strength *x**i*, then Kirito loses the duel and dies. But if Kirito's strength is greater than the dragon's strength, then he defeats the dragon and gets a bonus strength increase by *y**i*.

Kirito can fight the dragons in any order. Determine whether he can move on to the next level of the game, that is, defeat all dragons without a single loss.

Input Specification:
The first line contains two space-separated integers *s* and *n* (1<=≤<=*s*<=≤<=104, 1<=≤<=*n*<=≤<=103). Then *n* lines follow: the *i*-th line contains space-separated integers *x**i* and *y**i* (1<=≤<=*x**i*<=≤<=104, 0<=≤<=*y**i*<=≤<=104) — the *i*-th dragon's strength and the bonus for defeating it.

Output Specification:
On a single line print "YES" (without the quotes), if Kirito can move on to the next level and print "NO" (without the quotes), if he can't.

Demo Input:
['2 2\n1 99\n100 0\n', '10 1\n100 100\n']

Demo Output:
['YES\n', 'NO\n']

Note:
In the first sample Kirito's strength initially equals 2. As the first dragon's strength is less than 2, Kirito can fight it and defeat it. After that he gets the bonus and his strength increases to 2 + 99 = 101. Now he can defeat the second dragon and move on to the next level.

In the second sample Kirito's strength is too small to defeat the only dragon and win.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have an old building with n + 2 columns in a row. These columns support the ceiling. These columns are located in points with coordinates 0 = x0 < x1 < ... < xn < xn + 1. The leftmost and the rightmost columns are special, we will call them bearing, the other columns are ordinary. 

For each column we know its durability di. Let's consider an ordinary column with coordinate x. Let's assume that the coordinate of the closest to it column to the left (bearing or ordinary) is a and the coordinate of the closest to it column to the right (also, bearing or ordinary) is b. In this task let's assume that this column supports the segment of the ceiling from point <image> to point <image> (here both fractions are considered as real division). If the length of the segment of the ceiling supported by the column exceeds di, then the column cannot support it and it crashes after a while, and after that the load is being redistributeed between the neighbouring columns according to the same principle.

<image>

Thus, ordinary columns will be crashing for some time until the process stops at some state. One can prove that the set of the remaining columns doesn't depend on the order in which columns crash. If there are only two bearing columns left in the end, then we assume that the whole construction crashes under the weight of the roof. But if at least one ordinary column stays in addition to the bearing ones, then the building doesn't crash.

To make the building stronger, we can add one extra ordinary column of arbitrary durability d' at any (not necessarily integer) point 0 < x' < xn + 1. If point x' is already occupied by an ordinary column, it is replaced by a new one.

Your task is to find out: what minimal durability can the added column have so that the building doesn't crash?

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of ordinary columns.

The second line contains n + 2 integers x0, x1, ..., xn, xn + 1 (x0 = 0, xi < xi + 1 for 0 ≤ i ≤ n, xn + 1 ≤ 109) — the coordinates of the columns.

The third line contains n integers d1, d2, ..., dn (1 ≤ di ≤ 109).

Output

Print a single number — the minimum possible durability of the column that you need to add in order to make the building stay. If you do not have to add the column, please print 0. Your answer will be checked with the relative or absolute error 10 - 4.

Examples

Input

2
0 20 40 100
15 40


Output

10


Input

3
0 4 10 28 30
9 13 5


Output

0

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