vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
We have a deck consisting of N cards. Each card has an integer written on it. The integer on the i-th card from the top is a_i.
Two people X and Y will play a game using this deck. Initially, X has a card with Z written on it in his hand, and Y has a card with W written on it in his hand. Then, starting from X, they will alternately perform the following action:
 - Draw some number of cards from the top of the deck. Then, discard the card in his hand and keep the last drawn card instead. Here, at least one card must be drawn.
The game ends when there is no more card in the deck. The score of the game is the absolute difference of the integers written on the cards in the two players' hand.
X will play the game so that the score will be maximized, and Y will play the game so that the score will be minimized. What will be the score of the game?

-----Constraints-----
 - All input values are integers.
 - 1 \leq N \leq 2000
 - 1 \leq Z, W, a_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N Z W
a_1 a_2 ... a_N

-----Output-----
Print the score.

-----Sample Input-----
3 100 100
10 1000 100

-----Sample Output-----
900

If X draws two cards first, Y will draw the last card, and the score will be |1000 - 100| = 900.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree T that consists of N nodes. Each node is numbered from 1 to N, and node 1 is always the root node of T. Consider the following two operations on T:

* M v: (Mark) Mark node v.
* Q v: (Query) Print the index of the nearest marked ancestor of node v which is nearest to it. Initially, only the root node is marked. Note that a node is an ancestor of itself.



Your job is to write a program that performs a sequence of these operations on a given tree and calculates the value that each Q operation will print. To avoid too large output file, your program is requested to print the sum of the outputs of all query operations. Note that the judges confirmed that it is possible to calculate every output of query operations in a given sequence.



Input

The input consists of multiple datasets. Each dataset has the following format:

The first line of the input contains two integers N and Q, which denotes the number of nodes in the tree T and the number of operations, respectively. These numbers meet the following conditions: 1 ≤ N ≤ 100000 and 1 ≤ Q ≤ 100000.

The following N - 1 lines describe the configuration of the tree T. Each line contains a single integer pi (i = 2, ... , N), which represents the index of the parent of i-th node.

The next Q lines contain operations in order. Each operation is formatted as "M v" or "Q v", where v is the index of a node.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the sum of the outputs of all query operations in one line.

Example

Input

6 3
1
1
2
3
3
Q 5
M 3
Q 5
0 0


Output

4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Eli- 1 started a part-time job handing out leaflets for N seconds. Eli- 1 wants to hand out as many leaflets as possible with her special ability, Cloning. Eli- gen can perform two kinds of actions below.

* Clone herself and generate Eli- (gen + 1) . (one Eli- gen (cloning) and one Eli- (gen + 1) (cloned) exist as a result of Eli-gen 's cloning.) This action takes gen \times C ( C is a coefficient related to cloning. ) seconds.
* Hand out one leaflet. This action takes one second regardress of the generation ( =gen ).



They can not hand out leaflets while cloning. Given N and C , find the maximum number of leaflets Eli- 1 and her clones can hand out in total modulo 1000000007 (= 10^9 + 7).

Constraints

* 1 \leq Q \leq 100000 = 10^5
* 1 \leq N_q \leq 100000 = 10^5
* 1 \leq C_q \leq 20000 = 2 \times 10^4

Input

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


Q
N_1 C_1
:
N_Q C_Q


The input consists of multiple test cases. On line 1 , Q that represents the number of test cases is given. Each test case is given on the next Q lines. For the test case q ( 1 \leq q \leq Q ) , N_q and C_q are given separated by a single space. N_q and C_q represent the working time and the coefficient related to cloning for test case q respectively.

Output

For each test case, Print the maximum number of leaflets Eli- 1 and her clones can hand out modulo 1000000007 ( = 10^9 + 7 ).

Partial Scores

30 points will be awarded for passing the test set satisfying the condition: Q = 1 .

Another 270 points will be awarded for passing the test set without addtional constraints and you can get 300 points in total.

Examples

Input

2
20 8
20 12


Output

24
20


Input

1
20 3


Output

67


Input

1
200 1


Output

148322100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has the square chessboard of size n × n and m rooks. Initially the chessboard is empty. Vasya will consequently put the rooks on the board one after another.

The cell of the field is under rook's attack, if there is at least one rook located in the same row or in the same column with this cell. If there is a rook located in the cell, this cell is also under attack.

You are given the positions of the board where Vasya will put rooks. For each rook you have to determine the number of cells which are not under attack after Vasya puts it on the board.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ min(100 000, n^2)) — the size of the board and the number of rooks. 

Each of the next m lines contains integers x_{i} and y_{i} (1 ≤ x_{i}, y_{i} ≤ n) — the number of the row and the number of the column where Vasya will put the i-th rook. Vasya puts rooks on the board in the order they appear in the input. It is guaranteed that any cell will contain no more than one rook.


-----Output-----

Print m integer, the i-th of them should be equal to the number of cells that are not under attack after first i rooks are put.


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

Output
4 2 0 

Input
5 2
1 5
5 1

Output
16 9 

Input
100000 1
300 400

Output
9999800001 



-----Note-----

On the picture below show the state of the board after put each of the three rooks. The cells which painted with grey color is not under the attack.

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A simplified arithmetic expression (SAE) is an arithmetic expression defined by the following grammar:

  * <SAE> ::= <Number> | <SAE>+<SAE> | <SAE>*<SAE> | (<SAE>)
  * <Number> ::= <Digit> | <Digit><Number>
  * <Digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9



In other words it's a correct arithmetic expression that is allowed to contain brackets, numbers (possibly with leading zeros), multiplications and additions. For example expressions "(0+01)", "0" and "1*(0)" are simplified arithmetic expressions, but expressions "2-1", "+1" and "1+2)" are not.

Given a string s1s2...s|s| that represents a SAE; si denotes the i-th character of the string which can be either a digit ('0'-'9'), a plus sign ('+'), a multiplication sign ('*'), an opening round bracket '(' or a closing round bracket ')'.

A part slsl + 1...sr of this string is called a sub-expression if and only if it is a SAE.

You task is to answer m queries, each of which is a pair of integers li, ri (1 ≤ li ≤ ri ≤ |s|). For each query determine whether the corresponding part of the given string is a sub-expression and in case it's a sub-expression calculate its value modulo 1000000007 (109 + 7). The values should be calculated using standard operator priorities.

Input

The first line of the input contains non-empty string s (1 ≤ |s| ≤ 4·105) which represents a correct SAE. Each character of the string can be one of the following characters: '*', '+', '(', ')' or a digit ('0'-'9'). The expression might contain extra-huge numbers.

The second line contains an integer m (1 ≤ m ≤ 4·105) which is the number of queries. Each of the next m lines contains two space-separated integers li, ri (1 ≤ li ≤ ri ≤ |s|) — the i-th query.

Output

The i-th number of output should be the answer for the i-th query. If the i-th query corresponds to a valid sub-expression output the value of the sub-expression modulo 1000000007 (109 + 7). Otherwise output -1 as an answer for the query. Print numbers on separate lines.

Examples

Input

((1+2)*3+101*2)
6
8 14
1 6
2 10
11 14
5 5
4 5


Output

205
-1
10
2
2
-1


Input

(01)
1
1 4


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A new delivery of clothing has arrived today to the clothing store. This delivery consists of $a$ ties, $b$ scarves, $c$ vests and $d$ jackets.

The store does not sell single clothing items — instead, it sells suits of two types:  a suit of the first type consists of one tie and one jacket;  a suit of the second type consists of one scarf, one vest and one jacket. 

Each suit of the first type costs $e$ coins, and each suit of the second type costs $f$ coins.

Calculate the maximum possible cost of a set of suits that can be composed from the delivered clothing items. Note that one item cannot be used in more than one suit (though some items may be left unused).


-----Input-----

The first line contains one integer $a$ $(1 \le a \le 100\,000)$ — the number of ties.

The second line contains one integer $b$ $(1 \le b \le 100\,000)$ — the number of scarves.

The third line contains one integer $c$ $(1 \le c \le 100\,000)$ — the number of vests.

The fourth line contains one integer $d$ $(1 \le d \le 100\,000)$ — the number of jackets.

The fifth line contains one integer $e$ $(1 \le e \le 1\,000)$ — the cost of one suit of the first type.

The sixth line contains one integer $f$ $(1 \le f \le 1\,000)$ — the cost of one suit of the second type.


-----Output-----

Print one integer — the maximum total cost of some set of suits that can be composed from the delivered items. 


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

Output
6

Input
12
11
13
20
4
6

Output
102

Input
17
14
5
21
15
17

Output
325



-----Note-----

It is possible to compose three suits of the second type in the first example, and their total cost will be $6$. Since all jackets will be used, it's impossible to add anything to this set.

The best course of action in the second example is to compose nine suits of the first type and eleven suits of the second type. The total cost is $9 \cdot 4 + 11 \cdot 6 = 102$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A string S of lowercase letters is given.  Then, we may make any number of moves.
In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string.
Return the lexicographically smallest string we could have after any number of moves.
 

Example 1:
Input: S = "cba", K = 1
Output: "acb"
Explanation: 
In the first move, we move the 1st character ("c") to the end, obtaining the string "bac".
In the second move, we move the 1st character ("b") to the end, obtaining the final result "acb".


Example 2:
Input: S = "baaca", K = 3
Output: "aaabc"
Explanation: 
In the first move, we move the 1st character ("b") to the end, obtaining the string "aacab".
In the second move, we move the 3rd character ("c") to the end, obtaining the final result "aaabc".

 
Note:

1 <= K <= S.length <= 1000
S consists of lowercase letters only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As summer vacations are going on and as usual Chintu and Pintu are in village at their maternal grand-parent's home to spend their summers for "p" days.The most fascinating thing about that village is the trees loaded will juicy and delicious mangoes & both Chintu and Pintu being mango-lovers spend their whole day filling their tummy with those fruity mangoes.

Now they discovered a special tree of mango and both wanted to have it as it was the most juicy category of mango they have encountered in their life but unfortunately,that special tree gives a single mango in a day so it raised dispute between both Chintu and Pintu as who will eat that and after sometime they came to strategy to resolve this dispute,they decided to play game and the winner will get the golden opportunity to grab that special mango on "pth" day.

Game goes like this,as there were "x" numbers of wooden logs present and each of height "h" surrounding that special tree.Both Chintu and Pintu plays in turn.In each turn one chooses log and cut it into equal parts(greater than 1) and resulting height(necessarily an integer) of each piece being greater than or equal to "d".Now ,each resulting piece also serves as the wooden log in further game.They keep on playing this game until the one who can't make the valid choice looses the game and then the other one will have the hold of that special mango on that day.Chintu will play first.

INPUT:

First line contains the number of days p (1 ≤ p ≤ 10^4).

Following "p" lines will contain  three integers x,h,d(1 ≤ x,h,d ≤ 10^9).

OUTPUT:

Output the name of winner "Chintu" or "Pintu" for each day in separate line.

SAMPLE INPUT
2
2 1 1
1 2 1

SAMPLE OUTPUT
Pintu
Chintu

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Binary Town is holding its biennial elections. All $k$ positions on its council are open, and as usual Notnomde and Yraglac are the only ones running for each position.

Having long since abandoned quaint majority voting, Binary Town uses binary voting instead. In binary voting, all $v$ voters can cast any number of ballots, or not vote at all. The $k^\mathrm {th}$ least significant bits of the total number of ballots are then used to determine which candidate wins each position. That is, Notnomde wins position $j$ if the $j^\mathrm {th}$ least significant bit of the total number of ballots is $0$, otherwise Yraglac wins.

You know your neighbours well, and know exactly how many ballots $b_ i$ each one will cast if they choose to vote. For some reason, not everyone is happy with the electoral system so not everyone votes. Thankfully, you also know the probability $p_ i$ of each citizen voting.

Since you like Yraglac more than Notnomde, you want to cast the number of ballots which maximizes the expected number of positions held by Yraglac.

Suppose there are $k = 2$ positions and $v = 2$ voters, and you know with $50\% $ probability that the voter other than yourself will cast one ballot. If you cast one ballot, the total number of ballots could be $01_2$ or $10_2$ with equal probability, so the expected number of positions for Yraglac is $1$. If you cast two ballots, the total number of ballots could be $10_2$ or $11_2$ with equal probability, making Yraglac’s expected number of positions $1.5$. In this case, you then decide to cast two ballots since that maximizes Yraglac’s expected number of positions.

-----Input-----
The first line contains two space-separated integers $1 \leq k \leq 16$, the number of positions, and $2 \leq v \leq 100$, the number of voters (including yourself). It is followed by $v - 1$ lines, each containing two space-separated numbers: a decimal $0 \leq p_ i \leq 1$, the probability of voter $i$ casting ballots, and an integer $0 \leq b_ i \leq 2^k - 1$, the number of ballots voter $i$ would cast should they vote.

-----Output-----
Output on a single line the number of ballots $0 \leq b_ v \leq 2^k - 1$ you should cast to maximize the expected number of positions held by Yraglac. The answer is guaranteed to be unique.

-----Examples-----
Sample Input 1:
2 2
0.5 1
Sample Output 1:
2

Sample Input 2:
4 3
1 11
0.4 1
Sample Output 2:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In some countries building highways takes a lot of time... Maybe that's because there are many possiblities to construct a network of highways and engineers can't make up their minds which one to choose. Suppose we have a list of cities that can be connected directly. Your task is to count how many ways there are to build such a network that between every two cities there exists exactly one path. Two networks differ if there are two cities that are connected directly in the first case and aren't in the second case. At most one highway connects two cities. No highway connects a city to itself. Highways are two-way.  A path X-Y-W-A is the same as the path A-Y-W-A.


Input

The input is to be read from the standard input of your program. It begins with an integer 't', the number of test cases (equal to about 1000), followed by a new line, followed by the 't' test cases.


The first line of each test case contains two integers, the number of cities (1 ≤ n ≤ 12) and the number of direct connections between them.
Each next line contains two integers, which are the specific numbers of cities that can be connected. Cities are numbered from 1 to n.
Consecutive test cases are separated with one blank line. The last line of input is terminated by a newline.




Output

The number of ways to build the network, for every test case in a separate line. Assume that when there is only one city, the answer should be 1. The answer will fit in a signed 64-bit integer.


Example
Sample input:
4
4 5
3 4
4 2
2 3
1 2
1 3

2 1
2 1

1 0

3 3
1 2
2 3
3 1

Sample output:
8
1
1
3

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

In the city, a bus named Fibonacci runs on the road every day.

There are `n` stations on the route. The Bus runs from station1 to stationn.

At the departure station(station1), `k` passengers get on the bus. 

At the second station(station2), a certain number of passengers get on and the same number get off. There are still `k` passengers on the bus.

From station3 to stationn-1, the number of boarding and alighting passengers follows the following rule:

- At stationi, the number of people getting on is the sum of the number of people getting on at the two previous stations(stationi-1 and stationi-2)
- The number of people getting off is equal to the number of people getting on at the previous station(stationi-1).

At stationn, all the passengers get off the bus. 

Now, The numbers we know are: `k` passengers get on the bus at station1, `n` stations in total, `m` passengers get off the bus at stationn.

We want to know: How many passengers on the bus when the bus runs out stationx.

# Input

- `k`: The number of passengers get on the bus at station1.
  - `1 <= k <= 100`


- `n`: The total number of stations(1-based).
  - `6 <= n <= 30`


- `m`: The number of passengers get off the bus at stationn.
  - `1 <= m <= 10^10`


- `x`: Stationx(1-based). The station we need to calculate.
  - `3 <= m <= n-1`


- All inputs are valid integers.

# Output

An integer. The number of passengers on the bus when the bus runs out stationx.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Collatz Conjecture states that for any natural number n, if n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. If you repeat the process continuously for n, n will eventually reach 1.

For example, if n = 20, the resulting sequence will be:

[20, 10, 5, 16, 8, 4, 2, 1] 

Write a program that will output the length of the Collatz Conjecture for any given n. In the example above, the output would be 8.

For more reading see: http://en.wikipedia.org/wiki/Collatz_conjecture

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
During a New Year special offer the "Sudislavl Bars" offered *n* promo codes. Each promo code consists of exactly six digits and gives right to one free cocktail at the bar "Mosquito Shelter". Of course, all the promocodes differ.

As the "Mosquito Shelter" opens only at 9, and partying in Sudislavl usually begins at as early as 6, many problems may arise as to how to type a promotional code without errors. It is necessary to calculate such maximum *k*, that the promotional code could be uniquely identified if it was typed with no more than *k* errors. At that, *k*<==<=0 means that the promotional codes must be entered exactly.

A mistake in this problem should be considered as entering the wrong numbers. For example, value "123465" contains two errors relative to promocode "123456". Regardless of the number of errors the entered value consists of exactly six digits.

Input Specification:
The first line of the output contains number *n* (1<=≤<=*n*<=≤<=1000) — the number of promocodes.

Each of the next *n* lines contains a single promocode, consisting of exactly 6 digits. It is guaranteed that all the promocodes are distinct. Promocodes can start from digit "0".

Output Specification:
Print the maximum *k* (naturally, not exceeding the length of the promocode), such that any promocode can be uniquely identified if it is typed with at most *k* mistakes.

Demo Input:
['2\n000000\n999999\n', '6\n211111\n212111\n222111\n111111\n112111\n121111\n']

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

Note:
In the first sample *k* &lt; 3, so if a bar customer types in value "090909", then it will be impossible to define which promocode exactly corresponds to it.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Manao works on a sports TV. He's spent much time watching the football games of some country. After a while he began to notice different patterns. For example, each team has two sets of uniforms: home uniform and guest uniform. When a team plays a game at home, the players put on the home uniform. When a team plays as a guest on somebody else's stadium, the players put on the guest uniform. The only exception to that rule is: when the home uniform color of the host team matches the guests' uniform, the host team puts on its guest uniform as well. For each team the color of the home and guest uniform is different.

There are *n* teams taking part in the national championship. The championship consists of *n*·(*n*<=-<=1) games: each team invites each other team to its stadium. At this point Manao wondered: how many times during the championship is a host team going to put on the guest uniform? Note that the order of the games does not affect this number.

You know the colors of the home and guest uniform for each team. For simplicity, the colors are numbered by integers in such a way that no two distinct colors have the same number. Help Manao find the answer to his question.

Input Specification:
The first line contains an integer *n* (2<=≤<=*n*<=≤<=30). Each of the following *n* lines contains a pair of distinct space-separated integers *h**i*, *a**i* (1<=≤<=*h**i*,<=*a**i*<=≤<=100) — the colors of the *i*-th team's home and guest uniforms, respectively.

Output Specification:
In a single line print the number of games where the host team is going to play in the guest uniform.

Demo Input:
['3\n1 2\n2 4\n3 4\n', '4\n100 42\n42 100\n5 42\n100 5\n', '2\n1 2\n1 2\n']

Demo Output:
['1\n', '5\n', '0\n']

Note:
In the first test case the championship consists of 6 games. The only game with the event in question is the game between teams 2 and 1 on the stadium of team 2.

In the second test sample the host team will have to wear guest uniform in the games between teams: 1 and 2, 2 and 1, 2 and 3, 3 and 4, 4 and 2 (the host team is written first).

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