vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
General Iroh and Commandant Bumi are heading to the Republic City to stop a rebellion. But it's quite a long travel, so in the meantime they have started discussing about possible attacking plans. Right now, they're arguing about best ways for moving soldiers during the battle. Tired of not getting a final and concise strategy, Iroh proposed a particularly original idea.

Iroh:

Bumi, look at this map: here we have all possible locations in the battle field soldiers can occupy. I know a game which can give us some ideas.

Bumi:

A game? How will a game help us here?

Iroh:

It's pretty simple, we know which location is connected to each one, and also, that all those paths between locations are one-way (it's too dangerous to have two ways paths), so we place some soldiers at random initial locations, take turns, and in each turn, we try to make a valid move with one soldier from one location to another. Eventually, we won't be able to move any man so, the first one which is not able to perform any valid move, loses. One important thing is, at some moment, we may have some men at the same field location.

Bumi:

Are you sure we are gonna end this? We have so many locations and paths... don't know, soldiers could be moving in circles for ever.

Iroh:

Take it easy man, those paths were built by the best architects I've ever known, so there is no way that could happen.

Bumi:

Well, I still don't get how does this help us.

Iroh:

Me neither, but greatest generals from the Earth Kingdom created their strategies from this game, so, who knows?

Bumi:

Ok, I'm in. Who plays first?

Iroh:

You go first my friend. Just make sure you always do your best, because I will show no mercy to you :).

Input Format

First line in the input contains two integers N and M, describing the number of locations and paths between them, respectively. M lines follow, each one with two integers u and v, denoting a one-way path from u to v. 

Then comes a line with a single integer Q, denoting how many times Bumi and Iroh played the game over the given field. Q queries follow each one with two lines, first one with a single integer K, the number of soldiers in the field; and second one with K integers b_i separated by space, each one denoting the initial location of some soldier.

Constraints

$1 < N <= 10^{5} $

$1 <= M <= 10^{6} $

1 <= u, v, b_i <= N 

$1 <= K <= 10^{2} $

$1 <= Q <= 10^{5}  $

Output Format

Output Q lines, each one saying Bumi if Bumi should be the winner of the corresponding game or Iroh otherwise. 

Remember that, being both top strategy masters, they will always perform the best possible move each turn.

Sample Input
10 10
1 10
3 10
7 8
6 8
7 4
9 4
7 6
5 8
1 8
2 8
5
4
10 7 6 4
3
1 9 4
3
8 3 5
3
4 9 7
3
7 9 10

Sample Output
Bumi
Iroh
Iroh
Bumi
Bumi

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has n pairs of socks. In the morning of each day Vasya has to put on a pair of socks before he goes to school. When he comes home in the evening, Vasya takes off the used socks and throws them away. Every m-th day (at days with numbers m, 2m, 3m, ...) mom buys a pair of socks to Vasya. She does it late in the evening, so that Vasya cannot put on a new pair of socks before the next day. How many consecutive days pass until Vasya runs out of socks?


-----Input-----

The single line contains two integers n and m (1 ≤ n ≤ 100; 2 ≤ m ≤ 100), separated by a space.


-----Output-----

Print a single integer — the answer to the problem.


-----Examples-----
Input
2 2

Output
3

Input
9 3

Output
13



-----Note-----

In the first sample Vasya spends the first two days wearing the socks that he had initially. Then on day three he puts on the socks that were bought on day two.

In the second sample Vasya spends the first nine days wearing the socks that he had initially. Then he spends three days wearing the socks that were bought on the third, sixth and ninth days. Than he spends another day wearing the socks that were bought on the twelfth day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to solve some series problems, Chef wants your help to code it. Chef has one number N. Help the chef to find N'th number in the series.
0, 1, 5, 14, 30, 55 …..

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

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 10^4$
- $1 \leq N \leq 10^4$

-----Sample Input:-----
3
1
7
8

-----Sample Output:-----
0
91
140

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yaroslav is playing a game called "Time". The game has a timer showing the lifespan he's got left. As soon as the timer shows 0, Yaroslav's character dies and the game ends. Also, the game has n clock stations, station number i is at point (x_{i}, y_{i}) of the plane. As the player visits station number i, he increases the current time on his timer by a_{i}. The stations are for one-time use only, so if the player visits some station another time, the time on his timer won't grow.

A player spends d·dist time units to move between stations, where dist is the distance the player has covered and d is some constant. The distance between stations i and j is determined as |x_{i} - x_{j}| + |y_{i} - y_{j}|.

Initially, the player is at station number 1, and the player has strictly more than zero and strictly less than one units of time. At station number 1 one unit of money can increase the time on the timer by one time unit (you can buy only integer number of time units).

Now Yaroslav is wondering, how much money he needs to get to station n. Help Yaroslav. Consider the time to buy and to increase the timer value negligibly small.


-----Input-----

The first line contains integers n and d (3 ≤ n ≤ 100, 10^3 ≤ d ≤ 10^5) — the number of stations and the constant from the statement.

The second line contains n - 2 integers: a_2, a_3, ..., a_{n} - 1 (1 ≤ a_{i} ≤ 10^3). The next n lines contain the coordinates of the stations. The i-th of them contains two integers x_{i}, y_{i} (-100 ≤ x_{i}, y_{i} ≤ 100).

It is guaranteed that no two stations are located at the same point.


-----Output-----

In a single line print an integer — the answer to the problem.


-----Examples-----
Input
3 1000
1000
0 0
0 1
0 3

Output
2000

Input
3 1000
1000
1 0
1 1
1 2

Output
1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sherlock Holmes has decided to start a new academy to some of the young lads. He has conducted several tests and finally selected N equally brilliant

students.Now he don't know whether to train all the N students or not. Now since Holmes was in a confusion, Watson came up with an idea. He wanted to

test the obedience of the students. So during the camp, the students were given some Swiss Chocolates as gifts each time when they passed a level.Now some of them have

finished eating all the chocolates, some of them had some remaining. Now to test their team chemistry and IQ skills, Watson told the lads to arrange themselves in such 
a way that,  number of chocolates of the ith kid should be equal to the sum of   (i-1)th kid and (i-2)th kid. Now they have arranged themselves in an order.
Now Sherlock announced that he will select the students who have formed the line according to this order. But since there can be many such small groups among the

entire N kids, he will select a sequence of kids such that the length of the sequence is maximized, meanwhile satisfying the above condition 

-----Input-----
First line is an integer T which denotes the total number of test cases. Each of the next T lines contains an integer N which denotes, N students. The next 
line contains N spaced integers.where it denotes the order in which the kids arranged themselves. 

-----Output-----
Each line contains an integer which denotes the maximum number of students among the N students who have arranged themselves according the rule said by Watson.It is guaranteed that Holmes will select atleast 1 or 2 students

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 10^5
- 1 ≤ Each of next N integers ≤ 10^9

-----Subtasks-----
Subtask #1 : (20 points)
- 1 ≤ T ≤ 10
- 1 ≤ N≤ 100
- 1 ≤ Each element≤ 10^3

Subtask 2 : (80 points) 

- 1 ≤ T ≤ 10
- 1 ≤ N≤ 100000
- 1 ≤ Each element≤ 10^9

-----Example-----
Input:
2
5
2 3 5 1 2
3
1 2 3

Output:
3
3

-----Explanation-----
Example case 1. Here the first kid has 2 chocolates, second has 3 chocolates, third kid has 5 chocolates, which is the sum of first kid's total chocolates 
and second kid's chocolate. Forth student has only 1 chocolate where he did not follow the rule. So the maximum number of kids who arranged themselves in the order was 
3. That is students at index 1 to index 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Xrange makes the best polygonal pancakes in PancakeLand. To grow the business, they hired $m$ line cooks to be pancake rotators and flippers.

A regular n-gon has $n$ vertices, $n$ flipping axes, and $n$ rotation points. We define the following:

Flipping Axes 

If $n$ is odd, each flipping axis passes through a single vertex and the midpoint of the opposite side (resulting in $n$ total flipping axes).
If $n$ is even, $\frac{n}{2}$ flipping axes pass through every pair of opposing vertices and $\frac{n}{2}$ flipping axes pass through every pair of opposing sides.
The angle between consecutive axes is $\frac{360}{2n}$  degrees.
A $\boldsymbol{\mbox{k}}$-flipper flips the pancake at axis number $\boldsymbol{\mbox{k}}$.
Rotation Points 

There are $n$ types of rotators.
A $\boldsymbol{\mbox{k}}$-rotator rotates the the pancake clockwise by $\frac{\left(360\times k\right)}{n}$ degrees. The types of rotators are $\mbox{0}$-rotator, $\mbox{1}$-rotator, …, $(n-1)$-rotator.

Each pancake passes through a long line of rotators and flippers who change the polygonal pancake's orientation during cooking. Xrange wants to hire one more rotator or flipper to restore the pancake to its initial orientation for plating.

Given $n$ and the sequence of rotators and flippers that the pancake passes through, determine which type of rotator or flipper must be added to the end of the line to restore the pancake to its initial orientation.

Input Format

The first line contains two space-separated integers denoting the respective values of $n$ (the number of vertices in the polygonal pancake) and $m$ (the number of line cooks performing the transformations). 

Each line $\boldsymbol{i}$ of the $m$ subsequent lines describes a line cook in the form of two space-separated integers, $\textit{type}$ and $\boldsymbol{\mbox{k}}$ (respectively). If $\textit{type}=1$, line cook $\boldsymbol{i}$ is a rotator; if $\textit{type}=2$, line cook $\boldsymbol{i}$ is a flipper. The second value, $\boldsymbol{\mbox{k}}$, is the integer by which they flip or rotate the pancake; flippers flip the pancake along axis number $\boldsymbol{\mbox{k}}$, and rotators rotate the pancake by $\frac{360\times k}{n}$ degrees.

Constraints

$3\leq n\leq10^{6}$  
$1\leq m\leq10^6$  
$0\leq k<n$   

Output Format

Print a single line with two space-separated integers denoting the respective values of $\textit{type}$ and $\boldsymbol{\mbox{k}}$ for the rotator or flipper needed at the end of the line in order to restore the pancake to its initial orientation. 

Sample Input 0  

5 5
1 1
1 3
2 2
2 2
1 4

Sample Output 0  

1 2

Explanation 0  

The diagram below demonstrates the sequence of flips and rotations performed on the polygonal pancake as it makes its way down the line:

Once the pancake reaches the end of the line, it needs to be rotated (which is $\textit{type}=1$) by $k=2$ to be restored to its original orientation. Thus, we print 1 2 on a new line. 

Sample Input 1  

6 5
1 2
1 4
2 3
2 2
2 4

Sample Output 1  

2 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $5$ cities in the country.
The map of the country is given below.
The tour starts from the red city.

Each road is associated with a character.
Initially, there is an empty string.
Every time a road has been travelled the character associated gets appended to the string.
At the green city either the string can be printed or the tour can be continued.
In the problem, you are given a string tell whether it is possible to print the string while following the rules of the country?

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains a single line of input, a string $ s  $. The string consists only of $0's$ and $1's$.

-----Output:-----
For each testcase, output "YES" or "NO" depending on the input.

-----Constraints-----
- 
$1 \leq T \leq 10000$
- 
$1 \leq length of each string \leq 10000$
- 
$ 1 \leq Summation length \leq 10^5$

-----Sample Input:-----
1
100

-----Sample Output:-----
NO

-----EXPLANATION:-----

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Hideo Kojima has just quit his job at Konami. Now he is going to find a new place to work. Despite being such a well-known person, he still needs a CV to apply for a job.

During all his career Hideo has produced *n* games. Some of them were successful, some were not. Hideo wants to remove several of them (possibly zero) from his CV to make a better impression on employers. As a result there should be no unsuccessful game which comes right after successful one in his CV.

More formally, you are given an array *s*1,<=*s*2,<=...,<=*s**n* of zeros and ones. Zero corresponds to an unsuccessful game, one — to a successful one. Games are given in order they were produced, and Hideo can't swap these values. He should remove some elements from this array in such a way that no zero comes right after one.

Besides that, Hideo still wants to mention as much games in his CV as possible. Help this genius of a man determine the maximum number of games he can leave in his CV.

Input Specification:
The first line contains one integer number *n* (1<=≤<=*n*<=≤<=100).

The second line contains *n* space-separated integer numbers *s*1,<=*s*2,<=...,<=*s**n* (0<=≤<=*s**i*<=≤<=1). 0 corresponds to an unsuccessful game, 1 — to a successful one.

Output Specification:
Print one integer — the maximum number of games Hideo can leave in his CV so that no unsuccessful game comes after a successful one.

Demo Input:
['4\n1 1 0 1\n', '6\n0 1 0 0 1 0\n', '1\n0\n']

Demo Output:
['3\n', '4\n', '1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an equation: 

Ax2 + Bx + C = 0. 

Your task is to find the number of distinct roots of the equation and print all of them in ascending order.

Input

The first line contains three integer numbers A, B and C ( - 105 ≤ A, B, C ≤ 105). Any coefficient may be equal to 0.

Output

In case of infinite root count print the only integer -1. In case of no roots print the only integer 0. In other cases print the number of root on the first line and the roots on the following lines in the ascending order. Print roots with at least 5 digits after the decimal point.

Examples

Input

1 -5 6


Output

2
2.0000000000
3.0000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a permutation $p_1, p_2, \ldots, p_n$.

In one move you can swap two adjacent values.

You want to perform a minimum number of moves, such that in the end there will exist a subsegment $1,2,\ldots, k$, in other words in the end there should be an integer $i$, $1 \leq i \leq n-k+1$ such that $p_i = 1, p_{i+1} = 2, \ldots, p_{i+k-1}=k$.

Let $f(k)$ be the minimum number of moves that you need to make a subsegment with values $1,2,\ldots,k$ appear in the permutation.

You need to find $f(1), f(2), \ldots, f(n)$.


-----Input-----

The first line of input contains one integer $n$ ($1 \leq n \leq 200\,000$): the number of elements in the permutation.

The next line of input contains $n$ integers $p_1, p_2, \ldots, p_n$: given permutation ($1 \leq p_i \leq n$).


-----Output-----

Print $n$ integers, the minimum number of moves that you need to make a subsegment with values $1,2,\ldots,k$ appear in the permutation, for $k=1, 2, \ldots, n$.


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

Output
0 1 3 6 10 

Input
3
1 2 3

Output
0 0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hideyuki is allowed by his father Ujisato some 1000 yen bills every month for his pocket money. In the first day of every month, the number of bills is decided as follows. Ujisato prepares n pieces of m-sided dice and declares the cutback k. Hideyuki rolls these dice. The number of bills given is the sum of the spots of the rolled dice decreased by the cutback. Fortunately to Hideyuki, Ujisato promises him to give at least one bill, even if the sum of the spots does not exceed the cutback. Each of the dice has spots of 1 through m inclusive on each side, and the probability of each side is the same.

In this problem, you are asked to write a program that finds the expected value of the number of given bills.

For example, when n = 2, m = 6 and k = 3, the probabilities of the number of bills being 1, 2, 3, 4, 5, 6, 7, 8 and 9 are 1/36 + 2/36 + 3/36, 4/36, 5/36, 6/36, 5/36, 4/36, 3/36, 2/36 and 1/36, respectively.

Therefore, the expected value is

(1/36 + 2/36 + 3/36) × 1 + 4/36 × 2 + 5/36 × 3 + 6/36 × 4 + 5/36 × 5 + 4/36 × 6 + 3/36 × 7 + 2/36 × 8 + 1/36 × 9, which is approximately 4.11111111.



Input

The input is a sequence of lines each of which contains three integers n, m and k in this order. They satisfy the following conditions.

1 ≤ n
2 ≤ m
0 ≤ k < nm
nm × mn < 100000000 (108)


The end of the input is indicated by a line containing three zeros.

Output

The output should be comprised of lines each of which contains a single decimal fraction. It is the expected number of bills and may have an error less than 10-7 . No other characters should occur in the output.

Example

Input

2 6 0
2 6 3
3 10 9
13 3 27
1 2008 3
0 0 0


Output

7.00000000
4.11111111
7.71000000
1.42902599
1001.50298805

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Vasya likes very much to play with sets consisting of positive integers. To make the game more interesting, Vasya chose n non-empty sets in such a way, that no two of them have common elements.

One day he wanted to show his friends just how interesting playing with numbers is. For that he wrote out all possible unions of two different sets on n·(n - 1) / 2 pieces of paper. Then he shuffled the pieces of paper. He had written out the numbers in the unions in an arbitrary order.

For example, if n = 4, and the actual sets have the following form {1, 3}, {5}, {2, 4}, {7}, then the number of set pairs equals to six. The six pieces of paper can contain the following numbers: 

  * 2, 7, 4. 
  * 1, 7, 3; 
  * 5, 4, 2; 
  * 1, 3, 5; 
  * 3, 1, 2, 4; 
  * 5, 7. 



Then Vasya showed the pieces of paper to his friends, but kept the n sets secret from them. His friends managed to calculate which sets Vasya had thought of in the first place. And how about you, can you restore the sets by the given pieces of paper?

Input

The first input file line contains a number n (2 ≤ n ≤ 200), n is the number of sets at Vasya's disposal. Then follow sets of numbers from the pieces of paper written on n·(n - 1) / 2 lines. Each set starts with the number ki (2 ≤ ki ≤ 200), which is the number of numbers written of the i-th piece of paper, and then follow ki numbers aij (1 ≤ aij ≤ 200). All the numbers on the lines are separated by exactly one space. It is guaranteed that the input data is constructed according to the above given rules from n non-intersecting sets.

Output

Print on n lines Vasya's sets' description. The first number on the line shows how many numbers the current set has. Then the set should be recorded by listing its elements. Separate the numbers by spaces. Each number and each set should be printed exactly once. Print the sets and the numbers in the sets in any order. If there are several answers to that problem, print any of them.

It is guaranteed that there is a solution.

Examples

Input

4
3 2 7 4
3 1 7 3
3 5 4 2
3 1 3 5
4 3 1 2 4
2 5 7


Output

1 7 
2 2 4 
2 1 3 
1 5 


Input

4
5 6 7 8 9 100
4 7 8 9 1
4 7 8 9 2
3 1 6 100
3 2 6 100
2 1 2


Output

3 7 8 9 
2 6 100 
1 1 
1 2 


Input

3
2 1 2
2 1 3
2 2 3


Output

1 1 
1 2 
1 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 You are given an array of integers `arr` that representing coordinates of obstacles situated on a straight line.

 Assume that you are jumping from the point with coordinate 0 to the right. You are allowed only to make jumps of the same length represented by some integer.

 Find the minimal length of the jump enough to avoid all the obstacles.

# Example

 For `arr = [5, 3, 6, 7, 9]`, the output should be `4`.

 Check out the image below for better understanding:

 


# Input/Output


 - `[input]` integer array `arr`

    Non-empty array of positive integers.

    Constraints: `1 ≤ inputArray[i] ≤ 100.`


 - `[output]` an integer

    The desired length.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nastya is a competitive programmer, but she is only studying now. Recently, Denis told her about the way to check if the string is correct bracket sequence. After that, unexpectedly, Nastya came up with a much more complex problem that Denis couldn't solve. Can you solve it? 

A string s is given. It consists of k kinds of pairs of brackets. Each bracket has the form t — it is an integer, such that 1 ≤ |t| ≤ k. If the bracket has a form t, then: 

  * If t > 0, then it's an opening bracket of the type t. 
  * If t < 0, then it's a closing bracket of the type -t. 



Thus, there are k types of pairs of brackets in total. 

The queries need to be answered: 

  1. Replace the bracket at position i with the bracket of the form t. 
  2. Check if the substring from the l-th to r-th position (including) is the correct bracket sequence. 

Recall the definition of the correct bracket sequence: 
  * An empty sequence is correct. 
  * If A and B are two correct bracket sequences, then their concatenation "A B" is also correct bracket sequence. 
  * If A is the correct bracket sequence, c (1 ≤ c ≤ k) is a type of brackets, then the sequence "c A -c" is also correct bracket sequence. 

Input

The first line contains an integer n (1 ≤ n ≤ 10^5) — length of string and k (1 ≤ k ≤ n) — the number of kinds of pairs of brackets.

The second line contains string s of length n — n integers s_1, s_2, …, s_n (1 ≤ |s_i| ≤ k)

The third line contains single integer q (1 ≤ q ≤ 10^5) — the number of queries.

Each of the following q lines describes the queries: 

  * 1 i t - query of the 1 type (1 ≤ i ≤ n, 1 ≤ |t| ≤ k). 
  * 2 l r - query of the 2 type (1 ≤ l ≤ r ≤ n). 

Output

For each query of 2 type, output "Yes" if the substring from the query is the correct bracket sequence and "No", otherwise.

All letters can be displayed in any case.

Examples

Input


2 1
1 -1
1
2 1 2


Output


Yes


Input


2 2
1 -2
1
2 1 2


Output


No


Input


6 2
1 2 -2 -1 1 -1
3
2 1 6
2 1 4
2 2 5


Output


Yes
Yes
No


Input


2 2
-1 1
4
2 1 2
1 1 1
1 2 -1
2 1 2


Output


No
Yes

Note

In the fourth test, initially, the string is not a correct bracket sequence, so the answer to the first query is "No". After two changes it will be equal to "1 -1", so it is a correct bracket sequence and the answer to the fourth query is "Yes".

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