vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Babaei and Birthday Cake

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
As you know, every birthday party has a cake! This time, Babaei is going to prepare the very special birthday party's cake.

Simple cake is a cylinder of some radius and height. The volume of the simple cake is equal to the volume of corresponding cylinder. Babaei has *n* simple cakes and he is going to make a special cake placing some cylinders on each other.

However, there are some additional culinary restrictions. The cakes are numbered in such a way that the cake number *i* can be placed only on the table or on some cake number *j* where *j*<=&lt;<=*i*. Moreover, in order to impress friends Babaei will put the cake *i* on top of the cake *j* only if the volume of the cake *i* is strictly greater than the volume of the cake *j*.

Babaei wants to prepare a birthday cake that has a maximum possible total volume. Help him find this value.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=100<=000) — the number of simple cakes Babaei has.

Each of the following *n* lines contains two integers *r**i* and *h**i* (1<=≤<=*r**i*,<=*h**i*<=≤<=10<=000), giving the radius and height of the *i*-th cake.

Output Specification:
Print the maximum volume of the cake that Babaei can make. Your answer will be considered correct if its absolute or relative error does not exceed 10<=-<=6.

Namely: let's assume that your answer is *a*, and the answer of the jury is *b*. The checker program will consider your answer correct, if .

Demo Input:
['2\n100 30\n40 10\n', '4\n1 1\n9 7\n1 4\n10 7\n']

Demo Output:
['942477.796077000\n', '3983.539484752\n']

Note:
In first sample, the optimal way is to choose the cake number 1.

In second sample, the way to get the maximum volume is to use cakes with indices 1, 2 and 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As a part of this Kata, you need to create a function that when provided with a triplet, returns the index of the numerical element that lies between the other two elements.

The input to the function will be an array of three distinct numbers (Haskell: a tuple).

For example:

    gimme([2, 3, 1]) => 0

*2* is the number that fits between *1* and *3* and the index of *2* in the input array is *0*.

Another example (just to make sure it is clear):

    gimme([5, 10, 14]) => 1
    
*10* is the number that fits between *5* and *14* and the index of *10* in the input array is *1*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The students of college XYZ are getting jealous of the students of college ABC. ABC managed to beat XYZ 
in all the sports and games events. The main strength of the students of ABC is their unity. The students of 
XYZ decide to destroy this unity. The geeks of XYZ prepared a special kind of perfume. Anyone who inhales 
this perfume becomes extremely violent. The students of XYZ somehow manage to spread this perfume 
throughout ABC's campus atmosphere. 

There are N boys (1 , 2 , 3 , ..... N) and N girls (1 , 2 , 3 , ..... N) in ABC college. Each boy has a crush on a 
single girl and each girl has a crush on a single boy. Since the perfume has been inhaled by each and every 
student of ABC college, every student decides to beat up his/her crush's crush, ie. , if boy x has a crush on 
girl y and girl y has a crush on boy z, x will beat z up, provided, of course, if x and z is not the same person.

The doctor of ABC college foresees this situation. He cannot stop so many people from beating each other 
up, however, he can be prepared for the worst-case patient(s). The worst-case patient(s) will be the patient(s) who get(s) beaten up by the maximum number of students. The doctor comes to you for help. He has 2 questions for you :

1. What is the number of beatings received by the worst-case patient(s) ?

2. What is the total number of pairs of students who ended up beating up each other ?

Input :

The first line comprises of T, the number of test cases. Each test case comprises of 3 lines. The first line 
consists of N. 

The next line consists of N space separated natural numbers between 1 and N inclusive such that the ith 
number denotes the the crush of boy i.

The next line consists of N space separated natural numbers between 1 and N inclusive such that the ith 
number denotes the the crush of girl i.

Output :

For every test case, on a new line, print two space separated integers, the answer to doctor's question 1 followed by answer to doctor's question 2.

Constraints :

1 ≤ T ≤ 10

1 ≤ N ≤ 10^5

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

SAMPLE OUTPUT
1 0
1 4

Explanation

Test Case 1 :

Boy 1 likes Girl 2 and Girl 2 likes Boy 2. So, Boy 1 beats up Boy 2.
Boy 2 likes Girl 2 and Girl 2 likes Boy 2. Boy 2 is happy and will obviously not beat himself up.
Boy 3 likes Girl 1 and Girl 1 likes Boy 3. Boy 3 is happy and will obviously not beat himself up.
Girl 3 likes Boy 1 and Boy 1 likes Girl 2. So, Girl 3 beats up Girl 2.

Finally number of beatings received by :
Boy 1 = 0
Boy 2 = 1
Boy 3 = 0
Girl 1 = 0
Girl 2 = 1
Girl 3 = 0

Moreover, there are no such pairs of students who beat each other up. ie. there are no two students (boys or girls) i and j such that i beats up j and j beats up i. Hence the answer to test case 1 is '1 0'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A state with $n$ flags of ON or OFF can be represented by a sequence of bits where $0, 1, ..., n-1$ -th flag corresponds to 1 (ON) or 0 (OFF). The state can be managed by the corresponding decimal integer, because the sequence of bits is a binary representation where each bit is 0 or 1.

Given a sequence of bits with 64 flags which represent a state, perform the following operations. Note that each flag of the bits is initialized by OFF.

* test(i): Print 1 if $i$-th flag is ON, otherwise 0
* set(i): Set $i$-th flag to ON
* clear(i): Set $i$-th flag to OFF
* flip(i): Inverse $i$-th flag
* all: Print 1 if all flags are ON, otherwise 0
* any: Print 1 if at least one flag is ON, otherwise 0
* none: Print 1 if all flags are OFF, otherwise 0
* count: Print the number of ON flags
* val: Print the decimal value of the state

Constraints

* $1 \leq q \leq 200,000$
* $0 \leq i < 64$

Input

The input is given in the following format.


$q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given in the following format:


0 $i$


or


1 $i$


or


2 $i$


or


3 $i$


or


4


or


5


or


6


or


7


or


8


The first digit 0, 1,...,8 represents the operation test(i), set(i), clear(i), flip(i), all, any, none, count or val respectively.

Output

Print the result in a line for each test, all, any, none, count and val operation.

Example

Input

14
1 0
1 1
1 2
2 1
0 0
0 1
0 2
0 3
3 3
4
5
6
7
8


Output

1
0
1
0
0
1
0
3
13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Codehorses T-shirts

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Codehorses has just hosted the second Codehorses Cup. This year, the same as the previous one, organizers are giving T-shirts for the winners.

The valid sizes of T-shirts are either "M" or from $0$ to $3$ "X" followed by "S" or "L". For example, sizes "M", "XXS", "L", "XXXL" are valid and "XM", "Z", "XXXXL" are not.

There are $n$ winners to the cup for both the previous year and the current year. Ksenia has a list with the T-shirt sizes printed for the last year cup and is yet to send the new list to the printing office. 

Organizers want to distribute the prizes as soon as possible, so now Ksenia is required not to write the whole list from the scratch but just make some changes to the list of the previous year. In one second she can choose arbitrary position in any word and replace its character with some uppercase Latin letter. Ksenia can't remove or add letters in any of the words.

What is the minimal number of seconds Ksenia is required to spend to change the last year list to the current one?

The lists are unordered. That means, two lists are considered equal if and only if the number of occurrences of any string is the same in both lists.

Input Specification:
The first line contains one integer $n$ ($1 \le n \le 100$) — the number of T-shirts.

The $i$-th of the next $n$ lines contains $a_i$ — the size of the $i$-th T-shirt of the list for the previous year.

The $i$-th of the next $n$ lines contains $b_i$ — the size of the $i$-th T-shirt of the list for the current year.

It is guaranteed that all the sizes in the input are valid. It is also guaranteed that Ksenia can produce list $b$ from the list $a$.

Output Specification:
Print the minimal number of seconds Ksenia is required to spend to change the last year list to the current one. If the lists are already equal, print 0.

Demo Input:
['3\nXS\nXS\nM\nXL\nS\nXS\n', '2\nXXXL\nXXL\nXXL\nXXXS\n', '2\nM\nXS\nXS\nM\n']

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

Note:
In the first example Ksenia can replace "M" with "S" and "S" in one of the occurrences of "XS" with "L".

In the second example Ksenia should replace "L" in "XXXL" with "S".

In the third example lists are equal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A of length N. Find the number of pairs of indices (i,j) such that
1 ≤ i < j ≤ N
A_{i} \cdot A_{j} > 0

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

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the number of pairs which satisfy the above conditions.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$-10^{4} ≤ A_{i} ≤ 10^{4}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
5
1 -3 0 2 -1
4
-1 -1 -1 -1
4
0 1 2 3

----- Sample Output 1 ------ 
2
6
3

----- explanation 1 ------ 
Test case 1: The pairs which satisfy the conditions are $(1,4)$ and $(2,5)$.

Test case 2: The pairs which satisfy the conditions are $(1,2)$, $(1,3)$, $(1,4)$, $(2,3)$, $(2,4)$ and $(3,4)$.

Test case 3: The pairs which satisfy the conditions are $(2,3)$, $(2,4)$ and $(3,4)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob received an assignment from his school: he has two numbers A and B, and he has to find the sum of these two numbers.   
Alice, being a good friend of Bob, told him that the answer to this question is C.   
Bob doesn't completely trust Alice and asked you to tell him if the answer given by Alice is correct or not.   
If the answer is correct print "YES", otherwise print "NO" (without quotes).

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case consists of three space-separated integers A, B, and C.

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

For each test case, output on a new line the answer: YES if Alice gave the right answer, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, the outputs Yes, YES, yEs and yes will be treated as equivalent. 

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

$1 ≤ T ≤ 100$
$0 ≤ A , B , C ≤ 100$

----- Sample Input 1 ------ 
3
1 2 3
4 5 9
2 3 6
----- Sample Output 1 ------ 
YES
YES
NO
----- explanation 1 ------ 
Test case $1$: $1+2 = 3$, so Alice's answer is correct.

Test case $2$: $4+5 = 9$, so Alice's answer is correct.

Test case $3$: $2+3=5$ which doesn't equal $6$, so Alice's answer is incorrect.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Not everyone probably knows that Chef has younger brother Jeff. Currently Jeff learns to read.

He knows some subset of the letter of Latin alphabet. In order to help Jeff to study, Chef gave him a book with the text consisting of N words. Jeff can read a word iff it consists only of the letters he knows.

Now Chef is curious about which words his brother will be able to read, and which are not. Please help him!

------ Input ------ 

The first line of the input contains a lowercase Latin letter string S, consisting of the letters Jeff can read. Every letter will appear in S no more than once.

The second line of the input contains an integer N denoting the number of words in the book.

Each of the following N lines contains a single lowecase Latin letter string W_{i}, denoting the i^{th} word in the book.

------ Output ------ 

For each of the words, output "Yes" (without quotes) in case Jeff can read it, and "No" (without quotes) otherwise.

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

$1 ≤ |S| ≤ 26$
$1 ≤ N ≤ 1000$
$1 ≤ |W_{i}| ≤ 12$
$Each letter will appear in S no more than once.$
$S, W_{i} consist only of lowercase Latin letters.$

------ Subtasks ------ 

$Subtask #1 (31 point): |S| = 1, i.e. Jeff knows only one letter.$
$Subtask #2 (69 point)	: no additional constraints$

----- Sample Input 1 ------ 
act
2
cat
dog
----- Sample Output 1 ------ 
Yes
No
----- explanation 1 ------ 
The first word can be read.
The second word contains the letters d, o and g that aren't known by Jeff.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $N$ and $M$. Find the number of sequences $A_1, A_2, \ldots, A_N$, where each element is an integer between $1$ and $M$ (inclusive) and no three consecutive elements are equal. Since this number could be very large, compute it modulo $10^9+7$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $M$.

-----Output-----
For each test case, print a single line containing one integer ― the number of valid sequences modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le N, M \le 10^{18}$

-----Subtasks-----
Subtask #1 (50 points):
- $T \le 20$
- $N \le 10^5$
Subtask #2 (50 points): original constraints

-----Example Input-----
2 
2 2
3 4

-----Example Output-----
4
60

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are some animals in a garden. Each of them is a crane with two legs or a turtle with four legs.
Takahashi says: "there are X animals in total in the garden, and they have Y legs in total." Determine whether there is a combination of numbers of cranes and turtles in which this statement is correct.

-----Constraints-----
 - 1 \leq X \leq 100
 - 1 \leq Y \leq 100
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
X Y

-----Output-----
If there is a combination of numbers of cranes and turtles in which the statement is correct, print Yes; otherwise, print No.

-----Sample Input-----
3 8

-----Sample Output-----
Yes

The statement "there are 3 animals in total in the garden, and they have 8 legs in total" is correct if there are two cranes and one turtle. Thus, there is a combination of numbers of cranes and turtles in which the statement is correct.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Something happened in Uzhlyandia again... There are riots on the streets... Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arriving, they found that citizens are worried about maximum values of the Main Uzhlyandian Function *f*, which is defined as follows:

In the above formula, 1<=≤<=*l*<=&lt;<=*r*<=≤<=*n* must hold, where *n* is the size of the Main Uzhlyandian Array *a*, and |*x*| means absolute value of *x*. But the heroes skipped their math lessons in school, so they asked you for help. Help them calculate the maximum value of *f* among all possible values of *l* and *r* for the given array *a*.

Input Specification:
The first line contains single integer *n* (2<=≤<=*n*<=≤<=105) — the size of the array *a*.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (-109<=≤<=*a**i*<=≤<=109) — the array elements.

Output Specification:
Print the only integer — the maximum value of *f*.

Demo Input:
['5\n1 4 2 3 1\n', '4\n1 5 4 7\n']

Demo Output:
['3', '6']

Note:
In the first sample case, the optimal value of *f* is reached on intervals [1, 2] and [2, 5].

In the second case maximal value of *f* is reachable only on the whole array.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus participates in a competition for hacking into a new secure messenger. He's almost won.

Having carefully studied the interaction protocol, Polycarpus came to the conclusion that the secret key can be obtained if he properly cuts the public key of the application into two parts. The public key is a long integer which may consist of even a million digits!

Polycarpus needs to find such a way to cut the public key into two nonempty parts, that the first (left) part is divisible by *a* as a separate number, and the second (right) part is divisible by *b* as a separate number. Both parts should be positive integers that have no leading zeros. Polycarpus knows values *a* and *b*.

Help Polycarpus and find any suitable method to cut the public key.

Input Specification:
The first line of the input contains the public key of the messenger — an integer without leading zeroes, its length is in range from 1 to 106 digits. The second line contains a pair of space-separated positive integers *a*, *b* (1<=≤<=*a*,<=*b*<=≤<=108).

Output Specification:
In the first line print "YES" (without the quotes), if the method satisfying conditions above exists. In this case, next print two lines — the left and right parts after the cut. These two parts, being concatenated, must be exactly identical to the public key. The left part must be divisible by *a*, and the right part must be divisible by *b*. The two parts must be positive integers having no leading zeros. If there are several answers, print any of them.

If there is no answer, print in a single line "NO" (without the quotes).

Demo Input:
['116401024\n97 1024\n', '284254589153928171911281811000\n1009 1000\n', '120\n12 1\n']

Demo Output:
['YES\n11640\n1024\n', 'YES\n2842545891539\n28171911281811000\n', 'NO\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary string s consisting of n zeros and ones.

Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like "010101 ..." or "101010 ..." (i.e. the subsequence should not contain two adjacent zeros or ones).

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, subsequences of "1011101" are "0", "1", "11111", "0111", "101", "1001", but not "000", "101010" and "11100".

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of s. The second line of the test case contains n characters '0' and '1' — the string s.

It is guaranteed that the sum of n does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

Output

For each test case, print the answer: in the first line print one integer k (1 ≤ k ≤ n) — the minimum number of subsequences you can divide the string s to. In the second line print n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ k), where a_i is the number of subsequence the i-th character of s belongs to.

If there are several answers, you can print any.

Example

Input


4
4
0011
6
111111
5
10101
8
01010000


Output


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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Peace, which was supposed to last forever, suddenly ended. The Demon King, who had been sealed long ago, has finally revived. But when the world was about to be covered in darkness, a brave man appeared. The hero then set out on a journey to collect legendary crystals scattered around the world. Legend has it that if you can collect all the crystals, you can summon the legendary dragon god who can fulfill any wish. With the help of the dragon god, it should be possible to defeat the Demon King.

Crystals are scattered all over the world. The hero needs to collect them one by one by his own hands. This is because if someone other than the hero gets the crystal, it may be stolen by the Demon King's minions. A hero can travel only one Euclidean distance per day.

But there is one serious problem here. The Demon King constantly disperses the darkness of the miasma, and the place contaminated with the miasma turns into a land of death that no one can enter. Even a brave man cannot enter the place. Furthermore, since the miasma spreads concentrically with time, the area where the hero can move decreases with the passage of time. Miasma has been confirmed to spread by an Euclidean distance of 1 per day. And the hero cannot take the crystal on the boundary line. We also know that the newly resurrected Demon King will not move to store power.

The hero must get the crystal as soon as possible. But if it's not possible to get all the crystals, you'll have to think of another way. Therefore, I would like you to create a program to find out if you can get all the crystals from the initial position of the hero, the place where the demon king was resurrected, and the position where the crystals exist.

By the way, the brave does not get tired. And I don't sleep. Keep moving and collect crystals until you collect all the crystals and save the world! !!



Input

The input consists of multiple test cases. The first line of each test case gives the five integers n (0 <n <= 20), hx, hy, dx, and dy. n is the number of crystals, (hx, hy) is the position of the hero at the moment the Demon King was resurrected, and (dx, dy) is the position where the Demon King was resurrected. The n lines that follow are given the two integers cx, cy, that represent the position of each crystal. Input ends when n = hx = hy = dx = dy = 0, which is not included in the test case.

All coordinates given in the input are guaranteed to be integers with an absolute value of 1000 or less.

Output

For each test case, output "YES" if you can collect all the crystals, and "NO" if not.

Example

Input

2 0 0 10 10
1 1
4 4
2 0 0 10 10
1 1
6 6
2 0 0 10 10
1 1
5 5
0 0 0 0 0


Output

YES
NO
NO

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