vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Oscolcovo city has a campus consisting of n student dormitories, n universities and n military offices. Initially, the i-th dormitory belongs to the i-th university and is assigned to the i-th military office.

Life goes on and the campus is continuously going through some changes. The changes can be of four types:

  1. University aj merges with university bj. After that all the dormitories that belonged to university bj are assigned to to university aj, and university bj disappears. 
  2. Military office cj merges with military office dj. After that all the dormitories that were assigned to military office dj, are assigned to military office cj, and military office dj disappears. 
  3. Students of university xj move in dormitories. Lets kxj is the number of dormitories that belong to this university at the time when the students move in. Then the number of students in each dormitory of university xj increases by kxj (note that the more dormitories belong to the university, the more students move in each dormitory of the university). 
  4. Military office number yj conducts raids on all the dormitories assigned to it and takes all students from there. 



Thus, at each moment of time each dormitory is assigned to exactly one university and one military office. Initially, all the dormitory are empty.

Your task is to process the changes that take place in the campus and answer the queries, how many people currently live in dormitory qj.

Input

The first line contains two integers, n and m (1 ≤ n, m ≤ 5·105) — the number of dormitories and the number of queries, respectively.

Next m lines contain the queries, each of them is given in one of the following formats: 

  * «U aj bj» — merging universities; 
  * «M cj dj» — merging military offices; 
  * «A xj» — students of university xj moving in the dormitories; 
  * «Z yj» — a raid in military office yj; 
  * «Q qj» — a query asking the number of people in dormitory qj. 

All the numbers in the queries are positive integers and do not exceed n. It is guaranteed that at the moment of the query the universities and military offices, that are present in the query, exist.

Output

In the i-th line print the answer to the i-th query asking the number of people in the dormitory.

Examples

Input

2 7
A 1
Q 1
U 1 2
A 1
Z 1
Q 1
Q 2


Output

1
0
2


Input

5 12
U 1 2
M 4 5
A 1
Q 1
A 3
A 4
Q 3
Q 4
Z 4
Q 4
A 5
Q 5


Output

2
1
1
0
1

Note

Consider the first sample test: 

  * In the first query university 1 owns only dormitory 1, so after the query dormitory 1 will have 1 student. 
  * After the third query university 1 owns dormitories 1 and 2. 
  * The fourth query increases by 2 the number of students living in dormitories 1 and 2 that belong to university number 1. After that 3 students live in the first dormitory and 2 students live in the second dormitory. 
  * At the fifth query the number of students living in dormitory 1, assigned to the military office 1, becomes zero.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shakespeare is a widely known esoteric programming language in which programs look like plays by Shakespeare, and numbers are given by combinations of ornate epithets. In this problem we will have a closer look at the way the numbers are described in Shakespeare.

Each constant in Shakespeare is created from non-negative powers of 2 using arithmetic operations. For simplicity we'll allow only addition and subtraction and will look for a representation of the given number which requires a minimal number of operations.

You are given an integer n. You have to represent it as n = a1 + a2 + ... + am, where each of ai is a non-negative power of 2, possibly multiplied by -1. Find a representation which minimizes the value of m.

Input

The only line of input contains a positive integer n, written as its binary notation. The length of the notation is at most 106. The first digit of the notation is guaranteed to be 1.

Output

Output the required minimal m. After it output m lines. Each line has to be formatted as "+2^x" or "-2^x", where x is the power coefficient of the corresponding term. The order of the lines doesn't matter.

Examples

Input

1111


Output

2
+2^4
-2^0


Input

1010011


Output

4
+2^0
+2^1
+2^4
+2^6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the area of intersection between a circle $c$ and a polygon $g$. The center coordinate of the circle is ($0, 0$).

The polygon $g$ is represented by a sequence of points $p_1$, $p_2$,..., $p_n$ where line segments connecting $p_i$ and $p_{i+1}$ ($1 \leq i \leq n−1$) are sides of the polygon. The line segment connecting $p_n$ and $p_1$ is also a side of the polygon.

Note that the polygon is not necessarily convex.

Constraints

* $3 \leq n \leq 100$
* $1 \leq r \leq 100$
* $-100 \leq x_i, y_i \leq 100$

Input

The input is given in the following format.

$n$ $r$
$x_1$ $y_1$
$x_2$ $y_2$
:
$x_n$ $y_n$


In the first line, an integer n representing the number of points in the polygon is given. The coordinate of a point $p_i$ is given by two integers $x_i$ and $y_i$. The coordinates of the points are given in the order of counter-clockwise visit of them. All input values are given in integers.

Output

Print the area of intersection in a line. The output values should be in a decimal fraction with an error less than 0.00001.

Examples

Input

3 5
1 1
4 1
5 5


Output

4.639858417607


Input

4 5
0 0
-3 -6
1 -3
5 -4


Output

11.787686807576

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call two strings a and b (both of length k) a bit similar if they have the same character in some position, i. e. there exists at least one i ∈ [1, k] such that a_i = b_i.

You are given a binary string s of length n (a string of n characters 0 and/or 1) and an integer k. Let's denote the string s[i..j] as the substring of s starting from the i-th character and ending with the j-th character (that is, s[i..j] = s_i s_{i + 1} s_{i + 2} ... s_{j - 1} s_j).

Let's call a binary string t of length k beautiful if it is a bit similar to all substrings of s having length exactly k; that is, it is a bit similar to s[1..k], s[2..k+1], ..., s[n-k+1..n].

Your goal is to find the lexicographically smallest string t that is beautiful, or report that no such string exists. String x is lexicographically less than string y if either x is a prefix of y (and x ≠ y), or there exists such i (1 ≤ i ≤ min(|x|, |y|)), that x_i < y_i, and for any j (1 ≤ j < i) x_j = y_j.

Input

The first line contains one integer q (1 ≤ q ≤ 10000) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains two integers n and k (1 ≤ k ≤ n ≤ 10^6). The second line contains the string s, consisting of n characters (each character is either 0 or 1).

It is guaranteed that the sum of n over all test cases does not exceed 10^6.

Output

For each test case, print the answer as follows:

  * if it is impossible to construct a beautiful string, print one line containing the string NO (note: exactly in upper case, you can't print No, for example); 
  * otherwise, print two lines. The first line should contain the string YES (exactly in upper case as well); the second line — the lexicographically smallest beautiful string, consisting of k characters 0 and/or 1. 

Example

Input


7
4 2
0110
4 2
1001
9 3
010001110
9 3
101110001
10 3
0101110001
10 10
1111111111
11 10
11111111110


Output


YES
11
YES
00
YES
010
YES
101
NO
YES
0000000001
YES
0000000010

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bob has a permutation of integers from 1 to *n*. Denote this permutation as *p*. The *i*-th element of *p* will be denoted as *p**i*. For all pairs of distinct integers *i*,<=*j* between 1 and *n*, he wrote the number *a**i*,<=*j*<==<=*min*(*p**i*,<=*p**j*). He writes *a**i*,<=*i*<==<=0 for all integer *i* from 1 to *n*.

Bob gave you all the values of *a**i*,<=*j* that he wrote down. Your job is to reconstruct any permutation that could have generated these values. The input will be formed so that it is guaranteed that there is at least one solution that is consistent with the information given.

Input Specification:
The first line of the input will contain a single integer *n* (2<=≤<=*n*<=≤<=50).

The next *n* lines will contain the values of *a**i*,<=*j*. The *j*-th number on the *i*-th line will represent *a**i*,<=*j*. The *i*-th number on the *i*-th line will be 0. It's guaranteed that *a**i*,<=*j*<==<=*a**j*,<=*i* and there is at least one solution consistent with the information given.

Output Specification:
Print *n* space separated integers, which represents a permutation that could have generated these values. If there are multiple possible solutions, print any of them.

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

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

Note:
In the first case, the answer can be {1, 2} or {2, 1}.

In the second case, another possible answer is {2, 4, 5, 1, 3}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A bored technician whose job requires inspecting each of $10$ equipment stations on a regular basis has tried to inject a little variety into his days by creating a deck of cards, each card bearing a number in the range $1..10$. From this deck he randomly deals out $K$ cards at the start of the day, and uses the numbers on these to determine which stations and in what order he will visit them on that day. (He has decided that it is OK to visit the same station more than once in the same day.)

As time goes by, he adds cards for the number of stations where he finds problems, so that he will visit them more often, so the number of cards bearing each digit may vary considerably.

One day he deals out his cards, and notices that they have come out in strictly ascending order. He starts to wonder just how likely such an ordering would be.

Find the number of ways to deal the cards that form a strictly ascending sequence. (“Strictly ascending” in this problem means that, for example $[2, 4, 5]$ would be accepted but $[3, 1, 2]$ and $[2, 2, 4]$ would not.)

-----Input-----
The first line of input contains $10$ non-negative integers $n_ i$, each denoting the number of cards bearing the number $i$. The sum of these $10$ numbers is in the range $1\ldots 1000$.

This is followed by a line containing an integer $K$, $1 \leq K \leq 10$, denoting the number of cards to be dealt.

-----Output-----
Print a single line containing an integer denoting the number of ways to deal $K$ cards from that deck that would form a strictly ascending sequence.

-----Examples-----
Sample Input 1:
4 0 0 0 4 0 0 0 0 4
3
Sample Output 1:
64

Sample Input 2:
4 0 0 0 4 0 0 0 0 4
4
Sample Output 2:
0

Sample Input 3:
10 10 10 20 0 10 10 10 10 10
4
Sample Output 3:
1820000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
ByteLand is a large country with a tree-like road system. It has $N$ cities and $(N-1)$ unidirected roads. The capital of ByteLand is a city, numbered $\mbox{1}$, and all the roads go away from the capital. So people use these roads to reach any city from the capital. But it is impossible to reach the capital from a city by roads. 

To solve this problem, there is a system of teleporters. Each city has a teleporter in it. Each teleporter has a value of strength. Let's say, the $\boldsymbol{i}$-th one has the value of strength equal to $A_i$. This means that by using the teleporter, you'll become $A_i$ cities close to the capital (the same as going $A_i$ roads in the capital direction). If the distance to the capital is less than $A_i$, you'll simply move to the capital instead.

The road system of ByteLand and the initial teleports' strengths will be given to you. You'll also be given $\mbox{M}$ queries about the teleport network in ByteLand. These queries will have one of the following forms:

$\mbox{1}$ $\mbox{X}$ $\mathbf{Y}$ : The strength of the teleport in the city with the number $\mbox{X}$ becomes equal to $\mathbf{Y}$;

$2$ $\mbox{X}$ : Please output the minimal number of teleports that needs to be used to get from the city with the number $\mbox{X}$ to the capital. We can use only teleports in this query, but not the roads!

Input Format

The first line of input will contain two space-separated integers $N$ and $\mbox{M}$.

The second line will contain $N$ space separated integers $A_1,A_2,\ldots,A_N$ - the initial strengths of the teleports.

The following $(N-1)$ lines will contain pairs of space separated positive integers $\mbox{X}$ and $\mathbf{Y}$ with the meaning that there is a road between the cities with the numbers $\mbox{X}$ and $\mathbf{Y}$.

Each of following $\mbox{M}$ lines will contain a query in one of the formats, described above.

Constraints  

1 <= N <= 100000 

1 <= M <= 100000 

1 <= A_{i} <= 10000

Output Format

For each query of the second type, output an answer on a separate line. 

Sample Input
5 2
1 2 1 2 1
1 2
2 3
3 4
4 5
2 4
2 5

Sample Output
2
3

Explanation

In the first query, we jump two cities up and appear in the second city, then we jump once more and move to the capital.

In the second query, we jump one city up and appear in the city $\begin{array}{c}4\end{array}$. From that city we need $2$ more teleportations to get to the capital (this is yet the first query).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
n children are standing in a circle and playing the counting-out game. Children are numbered clockwise from 1 to n. In the beginning, the first child is considered the leader. The game is played in k steps. In the i-th step the leader counts out a_{i} people in clockwise order, starting from the next person. The last one to be pointed at by the leader is eliminated, and the next player after him becomes the new leader.

For example, if there are children with numbers [8, 10, 13, 14, 16] currently in the circle, the leader is child 13 and a_{i} = 12, then counting-out rhyme ends on child 16, who is eliminated. Child 8 becomes the leader.

You have to write a program which prints the number of the child to be eliminated on every step.


-----Input-----

The first line contains two integer numbers n and k (2 ≤ n ≤ 100, 1 ≤ k ≤ n - 1).

The next line contains k integer numbers a_1, a_2, ..., a_{k} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print k numbers, the i-th one corresponds to the number of child to be eliminated at the i-th step.


-----Examples-----
Input
7 5
10 4 11 4 1

Output
4 2 5 6 1 

Input
3 2
2 5

Output
3 2 



-----Note-----

Let's consider first example:   In the first step child 4 is eliminated, child 5 becomes the leader.  In the second step child 2 is eliminated, child 3 becomes the leader.  In the third step child 5 is eliminated, child 6 becomes the leader.  In the fourth step child 6 is eliminated, child 7 becomes the leader.  In the final step child 1 is eliminated, child 3 becomes the leader.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string s, consisting only of characters '0' or '1'. Let |s| be the length of s.

You are asked to choose some integer k (k > 0) and find a sequence a of length k such that: 

  * 1 ≤ a_1 < a_2 < ... < a_k ≤ |s|; 
  * a_{i-1} + 1 < a_i for all i from 2 to k. 



The characters at positions a_1, a_2, ..., a_k are removed, the remaining characters are concatenated without changing the order. So, in other words, the positions in the sequence a should not be adjacent.

Let the resulting string be s'. s' is called sorted if for all i from 2 to |s'| s'_{i-1} ≤ s'_i.

Does there exist such a sequence a that the resulting string s' is sorted?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

Then the descriptions of t testcases follow.

The only line of each testcase contains a string s (2 ≤ |s| ≤ 100). Each character is either '0' or '1'.

Output

For each testcase print "YES" if there exists a sequence a such that removing the characters at positions a_1, a_2, ..., a_k and concatenating the parts without changing the order produces a sorted string.

Otherwise, print "NO".

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

Example

Input


5
10101011011
0000
11111
110
1100


Output


YES
YES
YES
YES
NO

Note

In the first testcase you can choose a sequence a=[1,3,6,9]. Removing the underlined letters from "10101011011" will produce a string "0011111", which is sorted.

In the second and the third testcases the sequences are already sorted.

In the fourth testcase you can choose a sequence a=[3]. s'= "11", which is sorted.

In the fifth testcase there is no way to choose a sequence a such that s' is sorted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is the event manager of his college. He has been assigned the task to manage the upcoming tech fest. There are $K$ rooms where the event can take place, and at a particular time only one event can be organized in a room for a particular time interval.
Each event coordinator has their strictly preferred room $P_i$, and if the room is already occupied he simply cancels that event.Chef wants to maximize the total number of events,and so he allows or disallows certain events in order to achieve the task . Chef is busy handling his events so the chef needs your help .
Given a list of $N$ events with their start time $S_i$,end time $E_i$ and preferred room $P_i$,you need to calculate the maximum number of events that can take place.
Note that the $i$th event wants to occupy the $p_i$ room from [$s_i$, $f_i$) .

-----Input:-----
The first line contains an integer $T$ denoting the number of test cases . Each of the next $T$ lines contains two integers $N$ and $K$ , the number of events and the number of rooms respectively . Each of the next $N$ lines contains three integers $s_i$ ,$e_i$ and $p_i$,the start time ,end time and the preferred room of ith event.

-----Output:-----
Print the maximum number of events that can take place.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N \leq 10^3$
- $1 \leq  K \leq 10^5$
- $1 \leq  Si <  Ei \leq 10^9$
- $1 \leq Pi \leq K$

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

4 2
1 10 1
10 20 2
15 50 2
20 30 2

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

-----EXPLANATION:-----
Chef can allow events 1st ,2nd and 4th,to get the maximum 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string, consisting of lowercase Latin letters.

A pair of neighbouring letters in a string is considered ugly if these letters are also neighbouring in a alphabet. For example, string "abaca" contains ugly pairs at positions $(1, 2)$ — "ab" and $(2, 3)$ — "ba". Letters 'a' and 'z' aren't considered neighbouring in a alphabet.

Can you rearrange the letters of a given string so that there are no ugly pairs? You can choose any order of the letters of the given string but you can't add any new letters or remove the existing ones. You can also leave the order the same.

If there are multiple answers, print any of them.

You also have to answer $T$ separate queries.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 100$) — the number of queries.

Each of the next $T$ lines contains string $s$ $(1 \le |s| \le 100)$ — the string for the next query. It is guaranteed that it contains only lowercase Latin letters.

Note that in hacks you have to set $T = 1$.


-----Output-----

Print $T$ lines. The $i$-th line should contain the answer to the $i$-th query.

If the answer for the $i$-th query exists, then print such a rearrangment of letters of the given string that it contains no ugly pairs. You can choose any order of the letters of the given string but you can't add any new letters or remove the existing ones. You can also leave the order the same.

If there are multiple answers, print any of them.

Otherwise print "No answer" for that query.


-----Example-----
Input
4
abcd
gg
codeforces
abaca

Output
cadb
gg
codfoerces
No answer



-----Note-----

In the first example answer "bdac" is also correct.

The second example showcases the fact that only neighbouring in alphabet letters are not allowed. The same letter is ok.

There are lots of valid answers for the third example.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given sequence *a*1,<=*a*2,<=...,<=*a**n* of integer numbers of length *n*. Your task is to find such subsequence that its sum is odd and maximum among all such subsequences. It's guaranteed that given sequence contains subsequence with odd sum.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You should write a program which finds sum of the best subsequence.

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

The second line contains *n* integer numbers *a*1,<=*a*2,<=...,<=*a**n* (<=-<=104<=≤<=*a**i*<=≤<=104). The sequence contains at least one subsequence with odd sum.

Output Specification:
Print sum of resulting subseqeuence.

Demo Input:
['4\n-2 2 -3 1\n', '3\n2 -5 -3\n']

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

Note:
In the first example sum of the second and the fourth elements is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.
Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).
It is guaranteed that there will be an answer.
 
Example 1:
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

Example 2:
Input: nums = [2,3,5,7,11], threshold = 11
Output: 3

Example 3:
Input: nums = [19], threshold = 5
Output: 4

 
Constraints:

1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <= threshold <= 10^6

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