vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Chef has started developing interest in playing chess, and was learning how the [Queen] moves. 

Chef has an empty N \times N chessboard. He places a Queen at (X, Y) and wonders - What are the number of cells that are under attack by the Queen? 

Notes:
The top-left cell is (1, 1), the top-right cell is (1, N), the bottom-left cell is (N,1) and the bottom-right cell is (N, N).
The Queen can be moved any number of unoccupied cells in a straight line vertically, horizontally, or diagonally.
The cell on which the Queen is present, is not said to be under attack by the Queen.

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first and only line of each test case contains three integers N, X and Y, as described in the problem statement. 

------ Output Format ------ 

For each test case, output in a single line, the total number of cells that are under attack by the Queen. 

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{6}$
$1 ≤ X, Y ≤ N$

----- Sample Input 1 ------ 
5
1 1 1
3 2 2
3 2 1
2 2 2
150 62 41

----- Sample Output 1 ------ 
0
8
6
3
527

----- explanation 1 ------ 
Test case 1: The only cell on the board is $(1,1)$. Since Queen stands on this cell, it is not under attack.

Test case 2: The Queen can attack the following cells: $\{(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)\}$.

Test case 3: The Queen can attack the following cells: $\{(1, 1), (1, 2), (2, 2), (2, 3), (3, 1), (3, 2)\}$.

Test case 4: The Queen can attack the following cells: $\{(1, 1), (1, 2), (2, 1)\}$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ilya plays a card game by the following rules.

A player has several cards. Each card contains two non-negative integers inscribed, one at the top of the card and one at the bottom. At the beginning of the round the player chooses one of his cards to play it. If the top of the card contains number *a**i*, and the bottom contains number *b**i*, then when the player is playing the card, he gets *a**i* points and also gets the opportunity to play additional *b**i* cards. After the playing the card is discarded.

More formally: let's say that there is a counter of the cards that can be played. At the beginning of the round the counter equals one. When a card is played, the counter decreases by one for the played card and increases by the number *b**i*, which is written at the bottom of the card. Then the played card is discarded. If after that the counter is not equal to zero, the player gets the opportunity to play another card from the remaining cards. The round ends when the counter reaches zero or the player runs out of cards.

Of course, Ilya wants to get as many points as possible. Can you determine the maximum number of points he can score provided that you know his cards?

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=1000) — the number of cards Ilya has.

Each of the next *n* lines contains two non-negative space-separated integers — *a**i* and *b**i* (0<=≤<=*a**i*,<=*b**i*<=≤<=104) — the numbers, written at the top and the bottom of the *i*-th card correspondingly.

Output Specification:
Print the single number — the maximum number of points you can score in one round by the described rules.

Demo Input:
['2\n1 0\n2 0\n', '3\n1 0\n2 0\n0 2\n']

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

Note:
In the first sample none of two cards brings extra moves, so you should play the one that will bring more points.

In the second sample you should first play the third card that doesn't bring any points but lets you play both remaining cards.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree of n nodes. The tree is rooted at node 1, which is not considered as a leaf regardless of its degree.

Each leaf of the tree has one of the two colors: red or blue. Leaf node v initially has color s_{v}.

The color of each of the internal nodes (including the root) is determined as follows. 

  * Let b be the number of blue immediate children, and r be the number of red immediate children of a given vertex. 
  * Then the color of this vertex is blue if and only if b - r ≥ k, otherwise red. 



Integer k is a parameter that is same for all the nodes.

You need to handle the following types of queries: 

  * 1 v: print the color of node v; 
  * 2 v c: change the color of leaf v to c (c = 0 means red, c = 1 means blue); 
  * 3 h: update the current value of k to h. 

Input

The first line of the input consists of two integers n and k (2 ≤ n ≤ 10^{5}, -n ≤ k ≤ n) — the number of nodes and the initial parameter k.

Each of the next n - 1 lines contains two integers u and v (1 ≤ u,v ≤ n), denoting that there is an edge between vertices u and v.

The next line consists of n space separated integers — the initial array s (-1 ≤ s_i ≤ 1). s_{i} = 0 means that the color of node i is red. s_{i} = 1 means that the color of node i is blue. s_{i} = -1 means that the node i is not a leaf.

The next line contains an integer q (1 ≤ q ≤ 10^5), the number of queries.

q lines follow, each containing a query in one of the following queries: 

  * 1 v (1 ≤ v ≤ n): print the color of node v; 
  * 2 v c (1 ≤ v ≤ n, c = 0 or c = 1): change the color of leaf v to c (c = 0 means red, c = 1 means blue). It is guaranteed that v is a leaf; 
  * 3 h (-n ≤ h ≤ n): update the current value of k to h. 

Output

For each query of the first type, print 0 if the color of vertex v is red, and 1 otherwise.

Example

Input


5 2
1 2
1 3
2 4
2 5
-1 -1 0 1 0
9
1 1
1 2
3 -2
1 1
1 2
3 1
2 5 1
1 1
1 2


Output


0
0
1
1
0
1

Note

Figures:

(i) The initial tree 

(ii) The tree after the 3rd query 

(iii) The tree after the 7th query 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Joisino is planning to open a shop in a shopping street.
Each of the five weekdays is divided into two periods, the morning and the evening. For each of those ten periods, a shop must be either open during the whole period, or closed during the whole period. Naturally, a shop must be open during at least one of those periods.
There are already N stores in the street, numbered 1 through N.
You are given information of the business hours of those shops, F_{i,j,k}. If F_{i,j,k}=1, Shop i is open during Period k on Day j (this notation is explained below); if F_{i,j,k}=0, Shop i is closed during that period. Here, the days of the week are denoted as follows. Monday: Day 1, Tuesday: Day 2, Wednesday: Day 3, Thursday: Day 4, Friday: Day 5. Also, the morning is denoted as Period 1, and the afternoon is denoted as Period 2.
Let c_i be the number of periods during which both Shop i and Joisino's shop are open. Then, the profit of Joisino's shop will be P_{1,c_1}+P_{2,c_2}+...+P_{N,c_N}.
Find the maximum possible profit of Joisino's shop when she decides whether her shop is open during each period, making sure that it is open during at least one period.

-----Constraints-----
 - 1≤N≤100
 - 0≤F_{i,j,k}≤1
 - For every integer i such that 1≤i≤N, there exists at least one pair (j,k) such that F_{i,j,k}=1.
 - -10^7≤P_{i,j}≤10^7
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
F_{1,1,1} F_{1,1,2} ... F_{1,5,1} F_{1,5,2}
:
F_{N,1,1} F_{N,1,2} ... F_{N,5,1} F_{N,5,2}
P_{1,0} ... P_{1,10}
:
P_{N,0} ... P_{N,10}

-----Output-----
Print the maximum possible profit of Joisino's shop.

-----Sample Input-----
1
1 1 0 1 0 0 0 1 0 1
3 4 5 6 7 8 9 -2 -3 4 -2

-----Sample Output-----
8

If her shop is open only during the periods when Shop 1 is opened, the profit will be 8, which is the maximum possible profit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the hard version of the problem. The difference between the versions is the constraint on $n$ and the required number of operations. You can make hacks only if all versions of the problem are solved.

There are two binary strings $a$ and $b$ of length $n$ (a binary string is a string consisting of symbols $0$ and $1$). In an operation, you select a prefix of $a$, and simultaneously invert the bits in the prefix ($0$ changes to $1$ and $1$ changes to $0$) and reverse the order of the bits in the prefix.

For example, if $a=001011$ and you select the prefix of length $3$, it becomes $011011$. Then if you select the entire string, it becomes $001001$.

Your task is to transform the string $a$ into $b$ in at most $2n$ operations. It can be proved that it is always possible.


-----Input-----

The first line contains a single integer $t$ ($1\le t\le 1000$)  — the number of test cases. Next $3t$ lines contain descriptions of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 10^5$)  — the length of the binary strings.

The next two lines contain two binary strings $a$ and $b$ of length $n$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.


-----Output-----

For each test case, output an integer $k$ ($0\le k\le 2n$), followed by $k$ integers $p_1,\ldots,p_k$ ($1\le p_i\le n$). Here $k$ is the number of operations you use and $p_i$ is the length of the prefix you flip in the $i$-th operation.


-----Example-----
Input
5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1

Output
3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1



-----Note-----

In the first test case, we have $01\to 11\to 00\to 10$.

In the second test case, we have $01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100$.

In the third test case, the strings are already the same. Another solution is to flip the prefix of length $2$, which will leave $a$ unchanged.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ksenia has ordinary pan scales and several weights of an equal mass. Ksenia has already put some weights on the scales, while other weights are untouched. Ksenia is now wondering whether it is possible to put all the remaining weights on the scales so that the scales were in equilibrium. 

The scales is in equilibrium if the total sum of weights on the left pan is equal to the total sum of weights on the right pan.


-----Input-----

The first line has a non-empty sequence of characters describing the scales. In this sequence, an uppercase English letter indicates a weight, and the symbol "|" indicates the delimiter (the character occurs in the sequence exactly once). All weights that are recorded in the sequence before the delimiter are initially on the left pan of the scale. All weights that are recorded in the sequence after the delimiter are initially on the right pan of the scale. 

The second line contains a non-empty sequence containing uppercase English letters. Each letter indicates a weight which is not used yet. 

It is guaranteed that all the English letters in the input data are different. It is guaranteed that the input does not contain any extra characters.


-----Output-----

If you cannot put all the weights on the scales so that the scales were in equilibrium, print string "Impossible". Otherwise, print the description of the resulting scales, copy the format of the input.

If there are multiple answers, print any of them.


-----Examples-----
Input
AC|T
L

Output
AC|TL

Input
|ABC
XYZ

Output
XYZ|ABC

Input
W|T
F

Output
Impossible

Input
ABC|
D

Output
Impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"Brute Force isn't as inefficient as you may think", said the professor behind his mystical silhouette, as the final line before the end of the semester course. 
The students chuckled amongst themselves, mistaking it for a joke. The gloomy Cryptography class had met its dead end, and the students submitted their final assignments: a digital lock fortified by a 512-bit variant of the SHA-2 encryption algorithm. As the students rose to leave, one of them, called Cal, stayed behind to notice something weird. He looked closely at the lock. 
The lock had the 10(0-9) digits on its keypad, and it had a master key of N digits. The lock would break the moment someone entered the digits of the master key in succession. Cal remembered his own lock's master key: 1901. And he realized that the moment anyone entered those digits in succession, his lock would break.  So as soon as someone entered a 1, followed immediately by a 9, followed immediately by a 0, and followed immediately by a 1... His lock would break. If someone entered a 1, and then entered something other than 9, then he had to start over. The digits before and after the required sequence would not really matter. 
Cal's best friend interrupted his thoughts, "What are you thinking, dude?"
Cal turned back and replied, "See. We think our lock is entirely secure. Suppose we had a 2-digit code, you'd think that since there are a 100 2-digit numbers - consider 00-09 as two-digit numbers as well - you'd think you would require 200 digits to be assured that you tried all combinations. But it can be done in a much smaller sequence of digits."
"For instance, if I wanted to try all 2-digit combinations, I'd start with 0010203... And so on. This way, in 7 digits, I have covered 2-digit numbers like 00, 01, 02, 03, 10 and 20."
"And with sufficient foresight, I can calculate the shortest string that will cover all N-digit numbers, that is – if you tell me how long your master key is (let’s call that length N), I will give you the shortest string that is guaranteed to have all N-digit numbers as substrings. That will guarantee that your lock can be broken."(Caution: Numbers like 00000 or 00023 are 5-digit numbers in cryptographic contexts.)
Can you figure out what Cal was thinking?

Input
A number N which indicates how many digits are required to break upon the lock. You are supposed to process all these numbers until you read a 0 as input.
1 < N < 10
Output
The shortest string that has all possible N-digit strings as its substrings.
(Note: Outputs for the bigger numbers are huge.)

SAMPLE INPUT
1
2
0

SAMPLE OUTPUT
0123456789
0010203040..7787988990
(Case 2 is partially hidden. The first and last 10 digits of the smallest string are given.)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Is there anything better than going to the zoo after a tiresome week at work? No wonder Grisha feels the same while spending the entire weekend accompanied by pretty striped zebras. 

Inspired by this adventure and an accidentally found plasticine pack (represented as a sequence of black and white stripes), Grisha now wants to select several consequent (contiguous) pieces of alternating colors to create a zebra. Let's call the number of selected pieces the length of the zebra.

Before assembling the zebra Grisha can make the following operation 0 or more times. He splits the sequence in some place into two parts, then reverses each of them and sticks them together again. For example, if Grisha has pieces in the order "bwbbw" (here 'b' denotes a black strip, and 'w' denotes a white strip), then he can split the sequence as bw|bbw (here the vertical bar represents the cut), reverse both parts and obtain "wbwbb".

Determine the maximum possible length of the zebra that Grisha can produce.

Input

The only line contains a string s (1 ≤ |s| ≤ 10^5, where |s| denotes the length of the string s) comprised of lowercase English letters 'b' and 'w' only, where 'w' denotes a white piece and 'b' denotes a black piece.

Output

Print a single integer — the maximum possible zebra length.

Examples

Input

bwwwbwwbw


Output

5


Input

bwwbwwb


Output

3

Note

In the first example one of the possible sequence of operations is bwwwbww|bw → w|wbwwwbwb → wbwbwwwbw, that gives the answer equal to 5.

In the second example no operation can increase the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are going to hold a competition of one-to-one game called AtCoder Janken. (Janken is the Japanese name for Rock-paper-scissors.)N players will participate in this competition, and they are given distinct integers from 1 through N.
The arena has M playing fields for two players. You need to assign each playing field two distinct integers between 1 and N (inclusive).
You cannot assign the same integer to multiple playing fields.
The competition consists of N rounds, each of which proceeds as follows:
 - For each player, if there is a playing field that is assigned the player's integer, the player goes to that field and fight the other player who comes there.
 - Then, each player adds 1 to its integer. If it becomes N+1, change it to 1.
You want to ensure that no player fights the same opponent more than once during the N rounds.
Print an assignment of integers to the playing fields satisfying this condition.
It can be proved that such an assignment always exists under the constraints given.

-----Constraints-----
 - 1 \leq M
 - M \times 2 +1 \leq N \leq 200000

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

-----Output-----
Print M lines in the format below.
The i-th line should contain the two integers a_i and b_i assigned to the i-th playing field.
a_1 b_1
a_2 b_2
:
a_M b_M

-----Sample Input-----
4 1

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

Let us call the four players A, B, C, and D, and assume that they are initially given the integers 1, 2, 3, and 4, respectively.
 - The 1-st round is fought by B and C, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 2, 3, 4, and 1, respectively.
 - The 2-nd round is fought by A and B, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 3, 4, 1, and 2, respectively.
 - The 3-rd round is fought by D and A, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 4, 1, 2, and 3, respectively.
 - The 4-th round is fought by C and D, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 1, 2, 3, and 4, respectively.
No player fights the same opponent more than once during the four rounds, so this solution will be accepted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a Binary Tree of size N, You have to count leaves in it. For example, there are two leaves in following tree
        1
     /      \
   10      39
  /
5
 
Example 1:
Input:
Given Tree is 
               4
             /   \
            8     10
           /     /   \
          7     5     1
         /
        3 
Output:
3
Explanation: 
Three leaves are 3 , 5 and 1.
 
Your Task:
You don't have to take input. Complete the function countLeaves() that takes root node of the given tree as parameter and returns the count of leaves in tree. The printing is done by the driver code.
 
Constraints:
1<= N <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a sequence of N integers A_1, \ldots, A_N.

Find the (multiplicative) inverse of the sum of the inverses of these numbers, \frac{1}{\frac{1}{A_1} + \ldots + \frac{1}{A_N}}.

Constraints

* 1 \leq N \leq 100
* 1 \leq A_i \leq 1000

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 \ldots A_N


Output

Print a decimal number (or an integer) representing the value of \frac{1}{\frac{1}{A_1} + \ldots + \frac{1}{A_N}}.

Your output will be judged correct when its absolute or relative error from the judge's output is at most 10^{-5}.

Examples

Input

2
10 30


Output

7.5


Input

3
200 200 200


Output

66.66666666666667


Input

1
1000


Output

1000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fibonacci numbers are the sequence of integers: *f*0<==<=0, *f*1<==<=1, *f*2<==<=1, *f*3<==<=2, *f*4<==<=3, *f*5<==<=5, ..., *f**n*<==<=*f**n*<=-<=2<=+<=*f**n*<=-<=1. So every next number is the sum of the previous two.

Bajtek has developed a nice way to compute Fibonacci numbers on a blackboard. First, he writes a 0. Then, below it, he writes a 1. Then he performs the following two operations:
 -  operation "T": replace the top number with the sum of both numbers; -  operation "B": replace the bottom number with the sum of both numbers. 
If he performs *n* operations, starting with "T" and then choosing operations alternately (so that the sequence of operations looks like "TBTBTBTB..."), the last number written will be equal to *f**n*<=+<=1.

Unfortunately, Bajtek sometimes makes mistakes and repeats an operation two or more times in a row. For example, if Bajtek wanted to compute *f*7, then he would want to do *n*<==<=6 operations: "TBTBTB". If he instead performs the sequence of operations "TTTBBT", then he will have made 3 mistakes, and he will incorrectly compute that the seventh Fibonacci number is 10. The number of mistakes in the sequence of operations is the number of neighbouring equal operations («TT» or «BB»).

You are given the number *n* of operations that Bajtek has made in an attempt to compute *f**n*<=+<=1 and the number *r* that is the result of his computations (that is last written number). Find the minimum possible number of mistakes that Bajtek must have made and any possible sequence of *n* operations resulting in *r* with that number of mistakes.

Assume that Bajtek always correctly starts with operation "T".

Input Specification:
The first line contains the integers *n* and *r* (1<=≤<=*n*,<=*r*<=≤<=106).

Output Specification:
The first line of the output should contain one number — the minimum possible number of mistakes made by Bajtek. The second line should contain *n* characters, starting with "T", describing one possible sequence of operations with that number of mistakes. Each character must be either "T" or "B".

If the required sequence doesn't exist, output "IMPOSSIBLE" (without quotes).

Demo Input:
['6 10\n', '4 5\n', '2 1\n']

Demo Output:
['2\nTBBTTB\n', '0\nTBTB\n', 'IMPOSSIBLE\n']

Note:
none

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