vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Pink Floyd are pulling a prank on Roger Waters. They know he doesn't like walls, he wants to be able to walk freely, so they are blocking him from exiting his room which can be seen as a grid.

Roger Waters has a square grid of size $n\times n$ and he wants to traverse his grid from the upper left ($1,1$) corner to the lower right corner ($n,n$). Waters can move from a square to any other square adjacent by a side, as long as he is still in the grid. Also except for the cells ($1,1$) and ($n,n$) every cell has a value $0$ or $1$ in it.

Before starting his traversal he will pick either a $0$ or a $1$ and will be able to only go to cells values in which are equal to the digit he chose. The starting and finishing cells ($1,1$) and ($n,n$) are exempt from this rule, he may go through them regardless of picked digit. Because of this the cell ($1,1$) takes value the letter 'S' and the cell ($n,n$) takes value the letter 'F'.

For example, in the first example test case, he can go from ($1, 1$) to ($n, n$) by using the zeroes on this path: ($1, 1$), ($2, 1$), ($2, 2$), ($2, 3$), ($3, 3$), ($3, 4$), ($4, 4$)

The rest of the band (Pink Floyd) wants Waters to not be able to do his traversal, so while he is not looking they will invert at most two cells in the grid (from $0$ to $1$ or vice versa). They are afraid they will not be quick enough and asked for your help in choosing the cells.  Note that you cannot invert cells $(1, 1)$ and $(n, n)$.

We can show that there always exists a solution for the given constraints.

Also note that Waters will pick his digit of the traversal after the band has changed his grid, so he must not be able to reach ($n,n$) no matter what digit he picks.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50$). Description of the test cases follows.

The first line of each test case contains one integers $n$ ($3 \le n \le 200$).

The following $n$ lines of each test case contain the binary grid, square ($1, 1$) being colored in 'S' and square ($n, n$) being colored in 'F'.

The sum of values of $n$ doesn't exceed $200$.


-----Output-----

For each test case output on the first line an integer $c$ ($0 \le c \le 2$)  — the number of inverted cells.

In $i$-th of the following $c$ lines, print the coordinates of the $i$-th cell you inverted. You may not invert the same cell twice.  Note that you cannot invert cells $(1, 1)$ and $(n, n)$.


-----Example-----
Input
3
4
S010
0001
1000
111F
3
S10
101
01F
5
S0101
00000
01111
11111
0001F

Output
1
3 4
2
1 2
2 1
0



-----Note-----

For the first test case, after inverting the cell, we get the following grid:



S010

0001

1001

111F

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Abendsen assigned a mission to Juliana. In this mission, Juliana has a rooted tree with n vertices. Vertex number 1 is the root of this tree. Each vertex can be either black or white. At first, all vertices are white. Juliana is asked to process q queries. Each query is one of three types:

  1. If vertex v is white, mark it as black; otherwise, perform this operation on all direct sons of v instead. 
  2. Mark all vertices in the subtree of v (including v) as white. 
  3. Find the color of the i-th vertex. 

<image> An example of operation "1 1" (corresponds to the first example test). The vertices 1 and 2 are already black, so the operation goes to their sons instead.

Can you help Juliana to process all these queries?

Input

The first line contains two integers n and q (2≤ n≤ 10^5, 1≤ q≤ 10^5) — the number of vertices and the number of queries.

The second line contains n-1 integers p_2, p_3, …, p_n (1≤ p_i<i), where p_i means that there is an edge between vertices i and p_i. 

Each of the next q lines contains two integers t_i and v_i (1≤ t_i≤ 3, 1≤ v_i≤ n) — the type of the i-th query and the vertex of the i-th query.

It is guaranteed that the given graph is a tree.

Output

For each query of type 3, print "black" if the vertex is black; otherwise, print "white".

Examples

Input

8 10
1 2 1 2 5 4 5
1 2
3 2
3 1
1 1
1 1
3 5
3 7
3 4
2 2
3 5


Output

black
white
black
white
black
white


Input

8 11
1 1 2 3 3 6 6
1 1
1 1
1 3
3 2
3 4
3 6
3 7
2 3
1 6
3 7
3 6


Output

black
white
black
white
white
black

Note

The first example is shown on the picture below.

<image>

The second example is shown on the picture below.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem is given in two versions that differ only by constraints. If you can solve this problem in large constraints, then you can just write a single solution to the both versions. If you find the problem too difficult in large constraints, you can write solution to the simplified version only.

Waking up in the morning, Apollinaria decided to bake cookies. To bake one cookie, she needs n ingredients, and for each ingredient she knows the value a_{i} — how many grams of this ingredient one needs to bake a cookie. To prepare one cookie Apollinaria needs to use all n ingredients.

Apollinaria has b_{i} gram of the i-th ingredient. Also she has k grams of a magic powder. Each gram of magic powder can be turned to exactly 1 gram of any of the n ingredients and can be used for baking cookies.

Your task is to determine the maximum number of cookies, which Apollinaria is able to bake using the ingredients that she has and the magic powder.


-----Input-----

The first line of the input contains two positive integers n and k (1 ≤ n, k ≤ 1000) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000), where the i-th number is equal to the number of grams of the i-th ingredient, needed to bake one cookie.

The third line contains the sequence b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 1000), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.


-----Output-----

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.


-----Examples-----
Input
3 1
2 1 4
11 3 16

Output
4

Input
4 3
4 3 5 6
11 12 14 20

Output
3



-----Note-----

In the first sample it is profitably for Apollinaria to make the existing 1 gram of her magic powder to ingredient with the index 2, then Apollinaria will be able to bake 4 cookies.

In the second sample Apollinaria should turn 1 gram of magic powder to ingredient with the index 1 and 1 gram of magic powder to ingredient with the index 3. Then Apollinaria will be able to bake 3 cookies. The remaining 1 gram of the magic powder can be left, because it can't be used to increase the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today Oz wants to play with Lucky strings. A string S is called Lucky string if there exists a non-negative integer m such that S is composed of m consecutive 'R' characters followed by m consecutive 'K' characters. Empty string is also a Lucky string i.e for m=0
Now Oz has a string STR. Each character of STR is either 'R' or 'K'. Oz wants to change STR into a Lucky string by removing some of its characters without changing the order of the remaining characters. Oz wants to do this task by removing minimum number of characters. Help Oz to find the length of longest Lucky string he can get from STR.

Input :
The first line contains the number of test cases T. Each test case consists of a string STR.

Output :
For each test case output length of longest Lucky string Oz can get.

Constraint : 
1 ≤ T ≤ 50
1 ≤ |STR| ≤ 10^5

SAMPLE INPUT
2
KRKRKKR
KKKRRR

SAMPLE OUTPUT
4
0

Explanation

For first sample, Oz must remove the characters at indices 0,2,and 6 (0-based)
For second sample, Oz has to remove all characters of STR

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

AOR Co., Ltd. is a $ N $ story building. There is no basement floor.
AOR Ika-chan is a squid, so she can go down the stairs, but not up.

I decided to install $ M $ elevators in the building because it would be inconvenient if I couldn't climb upstairs.
It takes time to install the elevator, and the $ i $ th elevator will be installed the night after $ D_i $ and will be mobile on all floors above the $ A_i $ floor and below the $ B_i $ floor.

You were asked $ Q $ questions by AOR Ika-chan. The $ i $ th question is, "Can I move from the $ S_i $ floor to the $ T_i $ floor at noon $ E_i $ days later?"
The only means of transportation are stairs and elevators. In addition, the time required for movement shall be negligible.



input

$ N \ M \ Q $
$ D_1 \ A_1 \ B_1 $
$ \ vdots $
$ D_M \ A_M \ B_M $
$ E_1 \ S_1 \ T_1 $
$ \ vdots $
$ E_Q \ S_Q \ T_Q $

output

Print Yes or No on one line for each question. However, answer in the order in which they are asked. Also, output a line break at the end.

Example

Input

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


Output

No
Yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Its vacation time and Panda with two of his best friends Agham and Rishi is in his hometown, Pandaland. One day Panda came across a very delicious dish called PandaCake. He likes it very much and bought 'N' of them from a shop. Now on the day of his arrival i.e. on the first day, he ate only one PandaCake and decided to stay in Pandaland until he eats all the PandaCakes. If on any day he eats 'x' PandaCakes, then on next day he can eat either x or x-1 or x+1 PandaCakes. Also on last day he will eat only one PandaCake.

Help Panda calculate the minimum number of days required to complete his stay in Pandaland.  

INPUT:
The first line contains an integer T denoting the number of test cases.
Each of the next T lines contains an integer N.

OUTPUT:
T lines: Minimum number of days required for each test case.

CONSTRAINTS: 
T ≤ 100000
N ≤ 1000000000  

SAMPLE INPUT
3
5
1
4

SAMPLE OUTPUT
4
1
3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A student's life is fraught with complications. Some Berland University students know this only too well. Having studied for two years, they contracted strong antipathy towards the chairperson of some department. Indeed, the person in question wasn't the kindest of ladies to begin with: prone to reforming groups, banning automatic passes and other mean deeds. At last the students decided that she just can't get away with all this anymore...

The students pulled some strings on the higher levels and learned that the next University directors' meeting is going to discuss *n* orders about the chairperson and accept exactly *p* of them. There are two values assigned to each order: *a**i* is the number of the chairperson's hairs that turn grey if she obeys the order and *b**i* — the displeasement of the directors if the order isn't obeyed. The students may make the directors pass any *p* orders chosen by them. The students know that the chairperson will obey exactly *k* out of these *p* orders. She will pick the orders to obey in the way that minimizes first, the directors' displeasement and second, the number of hairs on her head that turn grey.

The students want to choose *p* orders in the way that maximizes the number of hairs on the chairperson's head that turn grey. If there are multiple ways to accept the orders, then the students are keen on maximizing the directors' displeasement with the chairperson's actions. Help them.

Input Specification:
The first line contains three integers *n* (1<=≤<=*n*<=≤<=105), *p* (1<=≤<=*p*<=≤<=*n*), *k* (1<=≤<=*k*<=≤<=*p*) — the number of orders the directors are going to discuss, the number of orders to pass and the number of orders to be obeyed by the chairperson, correspondingly. Each of the following *n* lines contains two integers *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=109), describing the corresponding order.

Output Specification:
Print in an arbitrary order *p* distinct integers — the numbers of the orders to accept so that the students could carry out the revenge. The orders are indexed from 1 to *n* in the order they occur in the input. If there are multiple solutions, you can print any of them.

Demo Input:
['5 3 2\n5 6\n5 8\n1 3\n4 3\n4 11\n', '5 3 3\n10 18\n18 17\n10 20\n20 18\n20 18\n']

Demo Output:
['3 1 2 ', '2 4 5 ']

Note:
In the first sample one of optimal solutions is to pass orders 1, 2, 3. In this case the chairperson obeys orders number 1 and 2. She gets 10 new grey hairs in the head and the directors' displeasement will equal 3. Note that the same result can be achieved with order 4 instead of order 3.

In the second sample, the chairperson can obey all the orders, so the best strategy for the students is to pick the orders with the maximum sum of *a*<sub class="lower-index">*i*</sub> values. The chairperson gets 58 new gray hairs and the directors' displeasement will equal 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N people standing in a queue from west to east.
Given is a string S of length N representing the directions of the people.
The i-th person from the west is facing west if the i-th character of S is L, and east if that character of S is R.
A person is happy if the person in front of him/her is facing the same direction.
If no person is standing in front of a person, however, he/she is not happy.
You can perform the following operation any number of times between 0 and K (inclusive):
Operation: Choose integers l and r such that 1 \leq l \leq r \leq N, and rotate by 180 degrees the part of the queue: the l-th, (l+1)-th, ..., r-th persons. That is, for each i = 0, 1, ..., r-l, the (l + i)-th person from the west will stand the (r - i)-th from the west after the operation, facing east if he/she is facing west now, and vice versa.
What is the maximum possible number of happy people you can have?

-----Constraints-----
 - N is an integer satisfying 1 \leq N \leq 10^5.
 - K is an integer satisfying 1 \leq K \leq 10^5.
 - |S| = N
 - Each character of S is L or R.

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

-----Output-----
Print the maximum possible number of happy people after at most K operations.

-----Sample Input-----
6 1
LRLRRL

-----Sample Output-----
3

If we choose (l, r) = (2, 5), we have LLLRLL, where the 2-nd, 3-rd, and 6-th persons from the west are happy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the number of pairs of non negative integers(n,m),such that 1 ≤ n<m ≤ k, where 2 ≤ k ≤ 1000000 and n|m^2 - 1 and m|n^2 - 1 ?

For integers m and n, it is said that m divides n, m is a divisor of n, or n is a multiple of m, and this is written as m | n,

Input :

first line conatins number of test case “T” and then T lines follows.
Each test case contains one integer "k".

Output:

For each test case print the number of pairs of non negative integers(n,m).

Constraints:

1 ≤ T ≤ 10

2 ≤ k ≤ 1000000

Sample input:

3

10

40

49

Ouptut:

18

82

101

SAMPLE INPUT
3
10
40
49

SAMPLE OUTPUT
18
82
101

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A biscuit making machine produces B biscuits at the following moments: A seconds, 2A seconds, 3A seconds and each subsequent multiple of A seconds after activation.
Find the total number of biscuits produced within T + 0.5 seconds after activation.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq A, B, T \leq 20

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

-----Output-----
Print the total number of biscuits produced within T + 0.5 seconds after activation.

-----Sample Input-----
3 5 7

-----Sample Output-----
10

 - Five biscuits will be produced three seconds after activation.
 - Another five biscuits will be produced six seconds after activation.
 - Thus, a total of ten biscuits will be produced within 7.5 seconds after activation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Constanze is the smartest girl in her village but she has bad eyesight.

One day, she was able to invent an incredible machine! When you pronounce letters, the machine will inscribe them onto a piece of paper. For example, if you pronounce 'c', 'o', 'd', and 'e' in that order, then the machine will inscribe "code" onto the paper. Thanks to this machine, she can finally write messages without using her glasses.

However, her dumb friend Akko decided to play a prank on her. Akko tinkered with the machine so that if you pronounce 'w', it will inscribe "uu" instead of "w", and if you pronounce 'm', it will inscribe "nn" instead of "m"! Since Constanze had bad eyesight, she was not able to realize what Akko did.

The rest of the letters behave the same as before: if you pronounce any letter besides 'w' and 'm', the machine will just inscribe it onto a piece of paper.

The next day, I received a letter in my mailbox. I can't understand it so I think it's either just some gibberish from Akko, or Constanze made it using her machine. But since I know what Akko did, I can just list down all possible strings that Constanze's machine would have turned into the message I got and see if anything makes sense.

But I need to know how much paper I will need, and that's why I'm asking you for help. Tell me the number of strings that Constanze's machine would've turned into the message I got.

But since this number can be quite large, tell me instead its remainder when divided by $10^9+7$.

If there are no strings that Constanze's machine would've turned into the message I got, then print $0$.


-----Input-----

Input consists of a single line containing a string $s$ ($1 \leq |s| \leq 10^5$) — the received message. $s$ contains only lowercase Latin letters.


-----Output-----

Print a single integer — the number of strings that Constanze's machine would've turned into the message $s$, modulo $10^9+7$.


-----Examples-----
Input
ouuokarinn

Output
4

Input
banana

Output
1

Input
nnn

Output
3

Input
amanda

Output
0



-----Note-----

For the first example, the candidate strings are the following: "ouuokarinn", "ouuokarim", "owokarim", and "owokarinn".

For the second example, there is only one: "banana".

For the third example, the candidate strings are the following: "nm", "mn" and "nnn".

For the last example, there are no candidate strings that the machine can turn into "amanda", since the machine won't inscribe 'm'.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mr. Santa asks all the great programmers of the world to solve a trivial problem. He gives them an integer *m* and asks for the number of positive integers *n*, such that the factorial of *n* ends with exactly *m* zeroes. Are you among those great programmers who can solve this problem?

Input Specification:
The only line of input contains an integer *m* (1<=≤<=*m*<=≤<=100<=000) — the required number of trailing zeroes in factorial.

Output Specification:
First print *k* — the number of values of *n* such that the factorial of *n* ends with *m* zeroes. Then print these *k* integers in increasing order.

Demo Input:
['1\n', '5\n']

Demo Output:
['5\n5 6 7 8 9 ', '0']

Note:
The factorial of *n* is equal to the product of all integers from 1 to *n* inclusive, that is *n*! = 1·2·3·...·*n*.

In the first sample, 5! = 120, 6! = 720, 7! = 5040, 8! = 40320 and 9! = 362880.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a public bath, there is a shower which emits water for T seconds when the switch is pushed.
If the switch is pushed when the shower is already emitting water, from that moment it will be emitting water for T seconds.
Note that it does not mean that the shower emits water for T additional seconds.
N people will push the switch while passing by the shower.
The i-th person will push the switch t_i seconds after the first person pushes it.
How long will the shower emit water in total?

-----Constraints-----
 - 1 ≤ N ≤ 200,000
 - 1 ≤ T ≤ 10^9
 - 0 = t_1 < t_2 < t_3 < , ..., < t_{N-1} < t_N ≤ 10^9
 - T and each t_i are integers.

-----Input-----
Input is given from Standard Input in the following format:
N T
t_1 t_2 ... t_N

-----Output-----
Assume that the shower will emit water for a total of X seconds. Print X.

-----Sample Input-----
2 4
0 3

-----Sample Output-----
7

Three seconds after the first person pushes the water, the switch is pushed again and the shower emits water for four more seconds, for a total of seven seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Appleman has a very big sheet of paper. This sheet has a form of rectangle with dimensions 1 × n. Your task is help Appleman with folding of such a sheet. Actually, you need to perform q queries. Each query will have one of the following types:  Fold the sheet of paper at position p_{i}. After this query the leftmost part of the paper with dimensions 1 × p_{i} must be above the rightmost part of the paper with dimensions 1 × ([current width of sheet] - p_{i}).  Count what is the total width of the paper pieces, if we will make two described later cuts and consider only the pieces between the cuts. We will make one cut at distance l_{i} from the left border of the current sheet of paper and the other at distance r_{i} from the left border of the current sheet of paper. 

Please look at the explanation of the first test example for better understanding of the problem.


-----Input-----

The first line contains two integers: n and q (1  ≤ n ≤ 10^5; 1 ≤ q ≤ 10^5) — the width of the paper and the number of queries.

Each of the following q lines contains one of the described queries in the following format:  "1 p_{i}" (1 ≤ p_{i} < [current width of sheet]) — the first type query.  "2 l_{i} r_{i}" (0 ≤ l_{i} < r_{i} ≤ [current width of sheet]) — the second type query. 


-----Output-----

For each query of the second type, output the answer.


-----Examples-----
Input
7 4
1 3
1 2
2 0 1
2 1 2

Output
4
3

Input
10 9
2 2 9
1 1
2 0 1
1 8
2 0 8
1 2
2 1 3
1 4
2 2 4

Output
7
2
10
4
5



-----Note-----

The pictures below show the shapes of the paper during the queries of the first example: [Image] 

After the first fold operation the sheet has width equal to 4, after the second one the width of the sheet equals to 2.

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