vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Berland has n cities, the capital is located in city s, and the historic home town of the President is in city t (s ≠ t). The cities are connected by one-way roads, the travel time for each of the road is a positive integer.

Once a year the President visited his historic home town t, for which his motorcade passes along some path from s to t (he always returns on a personal plane). Since the president is a very busy man, he always chooses the path from s to t, along which he will travel the fastest.

The ministry of Roads and Railways wants to learn for each of the road: whether the President will definitely pass through it during his travels, and if not, whether it is possible to repair it so that it would definitely be included in the shortest path from the capital to the historic home town of the President. Obviously, the road can not be repaired so that the travel time on it was less than one. The ministry of Berland, like any other, is interested in maintaining the budget, so it wants to know the minimum cost of repairing the road. Also, it is very fond of accuracy, so it repairs the roads so that the travel time on them is always a positive integer.


-----Input-----

The first lines contain four integers n, m, s and t (2 ≤ n ≤ 10^5; 1 ≤ m ≤ 10^5; 1 ≤ s, t ≤ n) — the number of cities and roads in Berland, the numbers of the capital and of the Presidents' home town (s ≠ t).

Next m lines contain the roads. Each road is given as a group of three integers a_{i}, b_{i}, l_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}; 1 ≤ l_{i} ≤ 10^6) — the cities that are connected by the i-th road and the time needed to ride along it. The road is directed from city a_{i} to city b_{i}.

The cities are numbered from 1 to n. Each pair of cities can have multiple roads between them. It is guaranteed that there is a path from s to t along the roads.


-----Output-----

Print m lines. The i-th line should contain information about the i-th road (the roads are numbered in the order of appearance in the input).

If the president will definitely ride along it during his travels, the line must contain a single word "YES" (without the quotes).

Otherwise, if the i-th road can be repaired so that the travel time on it remains positive and then president will definitely ride along it, print space-separated word "CAN" (without the quotes), and the minimum cost of repairing.

If we can't make the road be such that president will definitely ride along it, print "NO" (without the quotes).


-----Examples-----
Input
6 7 1 6
1 2 2
1 3 10
2 3 7
2 4 8
3 5 3
4 5 2
5 6 1

Output
YES
CAN 2
CAN 1
CAN 1
CAN 1
CAN 1
YES

Input
3 3 1 3
1 2 10
2 3 10
1 3 100

Output
YES
YES
CAN 81

Input
2 2 1 2
1 2 1
1 2 2

Output
YES
NO



-----Note-----

The cost of repairing the road is the difference between the time needed to ride along it before and after the repairing.

In the first sample president initially may choose one of the two following ways for a ride: 1 → 2 → 4 → 5 → 6 or 1 → 2 → 3 → 5 → 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mike Smith is a man exploring caves all over the world.

One day, he faced a scaring creature blocking his way. He got scared, but in short time he took his knife and then slashed it to attempt to kill it. Then they were split into parts, which soon died out but the largest one. He slashed the creature a couple of times more to make it small enough, and finally became able to go forward.

Now let us think of his situation in a mathematical way. The creature is considered to be a polygon, convex or concave. Mike slashes this creature straight with his knife in some direction. We suppose here the direction is given for simpler settings, while the position is arbitrary. Then all split parts but the largest one disappears.

Your task is to write a program that calculates the area of the remaining part when the creature is slashed in such a way that the area is minimized.



Input

The input is a sequence of datasets. Each dataset is given in the following format:

n
vx vy
x1 y1
...
xn yn

The first line contains an integer n, the number of vertices of the polygon that represents the shape of the creature (3 ≤ n ≤ 100). The next line contains two integers vx and vy, where (vx, vy) denote a vector that represents the direction of the knife (-10000 ≤ vx, vy ≤ 10000, vx2 + vy2 > 0). Then n lines follow. The i-th line contains two integers xi and yi, where (xi, yi) denote the coordinates of the i-th vertex of the polygon (0 ≤ xi, yi ≤ 10000).

The vertices are given in the counterclockwise order. You may assume the polygon is always simple, that is, the edges do not touch or cross each other except for end points.

The input is terminated by a line with a zero. This should not be processed.

Output

For each dataset, print the minimum possible area in a line. The area may be printed with an arbitrary number of digits after the decimal point, but should not contain an absolute error greater than 10-2.

Example

Input

5
0 1
0 0
5 0
1 1
5 2
0 2
7
9999 9998
0 0
2 0
3 1
1 1
10000 9999
2 2
0 2
0


Output

2.00
2.2500000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a string S consisting of `0` and `1`. Find the number of strings, modulo 998244353, that can result from applying the following operation on S between 0 and K times (inclusive):

* Choose a pair of integers i, j (1\leq i < j\leq |S|) such that the i-th and j-th characters of S are `0` and `1`, respectively. Remove the j-th character from S and insert it to the immediate left of the i-th character.

Constraints

* 1 \leq |S| \leq 300
* 0 \leq K \leq 10^9
* S consists of `0` and `1`.

Input

Input is given from Standard Input in the following format:


S K


Output

Find the number of strings, modulo 998244353, that can result from applying the operation on S between 0 and K times (inclusive).

Examples

Input

0101 1


Output

4


Input

01100110 2


Output

14


Input

1101010010101101110111100011011111011000111101110101010010101010101 20


Output

113434815

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

Betting on the lovely princess Claris, the duel between Tokitsukaze and Quailty has started.

There are $n$ cards in a row. Each card has two sides, one of which has color. At first, some of these cards are with color sides facing up and others are with color sides facing down. Then they take turns flipping cards, in which Tokitsukaze moves first. In each move, one should choose exactly $k$ consecutive cards and flip them to the same side, which means to make their color sides all face up or all face down. If all the color sides of these $n$ cards face the same direction after one's move, the one who takes this move will win.

Princess Claris wants to know who will win the game if Tokitsukaze and Quailty are so clever that they won't make mistakes.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$).

The second line contains a single string of length $n$ that only consists of $0$ and $1$, representing the situation of these $n$ cards, where the color side of the $i$-th card faces up if the $i$-th character is $1$, or otherwise, it faces down and the $i$-th character is $0$.


-----Output-----

Print "once again" (without quotes) if the total number of their moves can exceed $10^9$, which is considered a draw.

In other cases, print "tokitsukaze" (without quotes) if Tokitsukaze will win, or "quailty" (without quotes) if Quailty will win.

Note that the output characters are case-sensitive, and any wrong spelling would be rejected.


-----Examples-----
Input
4 2
0101

Output
quailty

Input
6 1
010101

Output
once again

Input
6 5
010101

Output
tokitsukaze

Input
4 1
0011

Output
once again



-----Note-----

In the first example, no matter how Tokitsukaze moves, there would be three cards with color sides facing the same direction after her move, and Quailty can flip the last card to this direction and win.

In the second example, no matter how Tokitsukaze moves, Quailty can choose the same card and flip back to the initial situation, which can allow the game to end in a draw.

In the third example, Tokitsukaze can win by flipping the leftmost five cards up or flipping the rightmost five cards down.

The fourth example can be explained in the same way as the second example does.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The students in a class in Akabe high-school define the relation “acquaintance” as:

* If A and B are friends, then A is acquainted with B.
* If A and B are friends and B is acquainted with C, then A is acquainted with C.



They define the relation “companion” as:

* Suppose A is acquainted with B, and two classmates who have been friend distance. If A is still acquainted with B, then A and B are companions.



A boy PCK joined the class recently and wishes to hold a party inviting his class fellows. He wishes to invite as many boys and girls as possible to the party and has written up an invitation list. In arranging the list, he placed the following conditions based on the acquaintanceship within the class before he joined.

When T is in the list:

* U is listed if he/she is a companion of T.
* If U is not a companion of T, U is not listed if he/she and T are friends, or he/she and some of T’s companions are friends.



PCK made the invitation list so that the maximum number of his classmates is included.

Given the number of classmates N and the friendships among them, write a program to estimate the number of boys and girls in the list. All the classmates are identified by an index that ranges from 0 to N-1.



Input

The input is given in the following format.


N M
s_1 t_1
s_2 t_2
:
s_M t_M


The first line provides the number of classmates N (2 ≤ N ≤ 105) and the number of friendships M (1 ≤ M ≤ 2×105). Each of the M subsequent lines provides two of the classmates s_i, t_i (0 ≤ s_i,t_i ≤ N-1) indicating they are friends. No duplicate relationship appears among these lines.

Output

Output the maximum number of classmates PCK invited to the party.

Examples

Input

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


Output

6


Input

3 2
0 1
1 2


Output

2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.

Given a sequence *a* consisting of *n* integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it *a**k*) and delete it, at that all elements equal to *a**k*<=+<=1 and *a**k*<=-<=1 also must be deleted from the sequence. That step brings *a**k* points to the player. 

Alex is a perfectionist, so he decided to get as many points as possible. Help him.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) that shows how many numbers are in Alex's sequence. 

The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=105).

Output Specification:
Print a single integer — the maximum number of points that Alex can earn.

Demo Input:
['2\n1 2\n', '3\n1 2 3\n', '9\n1 2 1 3 2 2 2 2 3\n']

Demo Output:
['2\n', '4\n', '10\n']

Note:
Consider the third test example. At first step we need to choose any element equal to 2. After that step our sequence looks like this [2, 2, 2, 2]. Then we do 4 steps, on each step we choose any element equals to 2. In total we earn 10 points.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a camp counselor at a summer camp and it is time to take some of the kids to lunch. There are $n$ groups of friends of different sizes who would like to be able to eat lunch together. There are $k$ bins that each hold exactly $x$ lunches. If one of the lunches in a bin is not used, then it must be thrown out due to health regulations.

If you take fewer than $a$ students to lunch then your fellow counselors will get angry as they have to watch the remaining campers. However, due to child safety regulations, you can watch at most $b$ children at any given time.

Is it possible to take a subset of the students to lunch such that the children get to eat with their friends, there are no wasted lunches, you take no more than the legal limit of campers, and you don’t anger your fellow counselors by taking too few?

-----Input-----
The first line contains one integer, $n$ ($1 \leq n \leq 1000$), the number of groups of friends. The next line contains $n$ space separated integers, $s_0, s_1, \ldots , s_{n-1}\ (0 < s_ i \leq 100)$, where $s_ i$ denotes the size of group $i$. The next line contains $4$ space separated integers: $k$ ($0 < k \leq 100$), $x$ ($0 < x \leq 100000$), $a$ and $b$ ($0 < a \leq b \leq 10000$) representing the number of bins, the number of lunches in each bin, the minimum number of campers you must watch, and the maximum number of campers you are allowed to watch, respectively.

-----Output-----
Output an integer denoting the maximum number of students you can take to lunch and satisfy the requirements, or, if it is not possible, output ‘impossible’.

-----Examples-----
Sample Input 1:
7
5 7 10 15 3 2 8
20 3 30 40
Sample Output 1:
39

Sample Input 2:
7
33 7 10 15 3 2 8
20 3 30 40
Sample Output 2:
36

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Chewbaсca and Number

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Luke Skywalker gave Chewbacca an integer number *x*. Chewbacca isn't good at numbers but he loves inverting digits in them. Inverting digit *t* means replacing it with digit 9<=-<=*t*. 

Help Chewbacca to transform the initial number *x* to the minimum possible positive number by inverting some (possibly, zero) digits. The decimal representation of the final number shouldn't start with a zero.

Input Specification:
The first line contains a single integer *x* (1<=≤<=*x*<=≤<=1018) — the number that Luke Skywalker gave to Chewbacca.

Output Specification:
Print the minimum possible positive number that Chewbacca can obtain after inverting some digits. The number shouldn't contain leading zeroes.

Demo Input:
['27\n', '4545\n']

Demo Output:
['22\n', '4444\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke participated in a magic show.

A magician prepared N identical-looking boxes. He put a treasure in one of the boxes, closed the boxes, shuffled them, and numbered them 1 through N.

Since the boxes are shuffled, now Snuke has no idea which box contains the treasure. Snuke wins the game if he opens a box containing the treasure. You may think that if Snuke opens all boxes at once, he can always win the game. However, there are some tricks:

* Snuke must open the boxes one by one. After he opens a box and checks the content of the box, he must close the box before opening the next box.
* He is only allowed to open Box i at most a_i times.
* The magician may secretly move the treasure from a closed box to another closed box, using some magic trick. For simplicity, assume that the magician never moves the treasure while Snuke is opening some box. However, he can move it at any other time (before Snuke opens the first box, or between he closes some box and opens the next box).
* The magician can perform the magic trick at most K times.



Can Snuke always win the game, regardless of the initial position of the treasure and the movements of the magician?

Constraints

* 2 \leq N \leq 50
* 1 \leq K \leq 50
* 1 \leq a_i \leq 100

Input

Input is given from Standard Input in the following format:


N K
a_1 a_2 \cdots a_N


Output

If the answer is no, print a single `-1`.

Otherwise, print one possible move of Snuke in the following format:


Q
x_1 x_2 \cdots x_Q


It means that he opens boxes x_1, x_2, \cdots, x_Q in this order.

In case there are multiple possible solutions, you can output any.

Examples

Input

2 1
5 5


Output

7
1 1 2 1 2 2 1


Input

3 50
5 10 15


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are some perfect squares with a particular property.
For example the number ```n = 256``` is a perfect square, its square root is ```16```. If we change the position of the digits of n, we may obtain another perfect square``` 625``` (square root = 25).
With these three digits ```2```,```5``` and ```6``` we can get two perfect squares: ```[256,625]```

The number ```1354896``` may generate another ```4``` perfect squares, having with the number itself, a total of five perfect squares: ```[1354896, 3594816, 3481956, 5391684, 6395841]```, being the last one in the list, ```6395841```, the highest value of the set.

Your task is to find the first perfect square above the given lower_limit, that can generate the given k number of perfect squares, and it doesn't contain the digit 0. Then return the maximum perfect square that can be obtained from its digits.

Example with the cases seen above:
```
lower_limit = 200
k = 2 (amount of perfect squares)
result = 625

lower_limit = 3550000
k = 5 (amount of perfect squares)
result  = 6395841
```
Features of the random tests:
```
100 <= lower_limit <= 1e6
2 <= k <= 5
number of tests = 45
```
Have a good time!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mislove had an array $a_1$, $a_2$, $\cdots$, $a_n$ of $n$ positive integers, but he has lost it. He only remembers the following facts about it:



 The number of different numbers in the array is not less than $l$ and is not greater than $r$;

 For each array's element $a_i$ either $a_i = 1$ or $a_i$ is even and there is a number $\dfrac{a_i}{2}$ in the array.

For example, if $n=5$, $l=2$, $r=3$ then an array could be $[1,2,2,4,4]$ or $[1,1,1,1,2]$; but it couldn't be $[1,2,2,4,8]$ because this array contains $4$ different numbers; it couldn't be $[1,2,2,3,3]$ because $3$ is odd and isn't equal to $1$; and it couldn't be $[1,1,2,2,16]$ because there is a number $16$ in the array but there isn't a number $\frac{16}{2} = 8$.

According to these facts, he is asking you to count the minimal and the maximal possible sums of all elements in an array. 


-----Input-----

The only input line contains three integers $n$, $l$ and $r$ ($1 \leq n \leq 1\,000$, $1 \leq l \leq r \leq \min(n, 20)$) — an array's size, the minimal number and the maximal number of distinct elements in an array.


-----Output-----

Output two numbers — the minimal and the maximal possible sums of all elements in an array.


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

Output
5 7

Input
5 1 5

Output
5 31



-----Note-----

In the first example, an array could be the one of the following: $[1,1,1,2]$, $[1,1,2,2]$ or $[1,2,2,2]$. In the first case the minimal sum is reached and in the last case the maximal sum is reached.

In the second example, the minimal sum is reached at the array $[1,1,1,1,1]$, and the maximal one is reached at the array $[1,2,4,8,16]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given the following concurrent program. There are N processes and the i-th process has the following pseudocode: 
    
    
    repeat ni times  
        yi := y  
        y := yi + 1  
    end repeat  
    

Here y is a shared variable. Everything else is local for the process. All actions on a given row are atomic, i.e. when the process starts executing a row it is never interrupted. Beyond that all interleavings are possible, i.e. every process that has yet work to do can be granted the rights to execute its next row. In the beginning y = 0. You will be given an integer W and ni, for i = 1, ... , N. Determine if it is possible that after all processes terminate, y = W, and if it is possible output an arbitrary schedule that will produce this final value.

Input

In the first line of the input you will be given two space separated integers N (1 ≤ N ≤ 100) and W ( - 109 ≤ W ≤ 109). In the second line there are N space separated integers ni (1 ≤ ni ≤ 1000).

Output

On the first line of the output write Yes if it is possible that at the end y = W, or No otherwise. If the answer is No then there is no second line, but if the answer is Yes, then on the second line output a space separated list of integers representing some schedule that leads to the desired result. For more information see note.

Examples

Input

1 10
11


Output

No


Input

2 3
4 4


Output

Yes
1 1 2 1 2 2 2 2 2 1 2 1 1 1 1 2


Input

3 6
1 2 3


Output

Yes
1 1 2 2 2 2 3 3 3 3 3 3

Note

For simplicity, assume that there is no repeat statement in the code of the processes, but the code from the loop is written the correct amount of times. The processes are numbered starting from 1. The list of integers represent which process works on its next instruction at a given step. For example, consider the schedule 1 2 2 1 3. First process 1 executes its first instruction, then process 2 executes its first two instructions, after that process 1 executes its second instruction, and finally process 3 executes its first instruction. The list must consists of exactly 2·Σ i = 1...N ni numbers.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a tree with N vertices, whose i-th edge connects Vertex u_i and Vertex v_i.
Vertex i has an integer a_i written on it.
For every integer k from 1 through N, solve the following problem:
 - We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex 1 to Vertex k, in the order they appear. Find the length of the longest increasing subsequence of this sequence.
Here, the longest increasing subsequence of a sequence A of length L is the subsequence A_{i_1} , A_{i_2} , ... , A_{i_M} with the greatest possible value of M such that 1 \leq i_1 < i_2 < ... < i_M \leq L and A_{i_1} < A_{i_2} < ... < A_{i_M}.

-----Constraints-----
 - 2 \leq N \leq 2 \times 10^5
 - 1 \leq a_i \leq 10^9
 - 1 \leq u_i , v_i \leq N
 - u_i \neq v_i
 - The given graph is a tree.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 a_2 ... a_N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}

-----Output-----
Print N lines. The k-th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex 1 to Vertex k.

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

-----Sample Output-----
1
2
3
3
4
4
5
2
2
3

For example, the sequence A obtained from the shortest path from Vertex 1 to Vertex 5 is 1,2,5,3,4. Its longest increasing subsequence is A_1, A_2, A_4, A_5, with the length of 4.

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