vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The new pedestrian zone in Moscow city center consists of n squares connected with each other by n - 1 footpaths. We define a simple path as a sequence of squares such that no square appears in this sequence twice and any two adjacent squares in this sequence are directly connected with a footpath. The size of a simple path is the number of squares in it. The footpaths are designed in a such a way that there is exactly one simple path between any pair of different squares.

During preparations for Moscow City Day the city council decided to renew ground tiles on all n squares. There are k tile types of different colors, numbered from 1 to k. For each square exactly one tile type must be selected and then used to cover this square surface. To make walking through the city center more fascinating, it was decided to select tiles types for each square in such a way that any possible simple path of size exactly k contains squares with all k possible tile colors.

You need to find out whether it is possible to place the tiles this way or not.

Input

The first line contains two integers n, k (2 ≤ k ≤ n ≤ 200 000) — the number of squares in the new pedestrian zone, the number of different tile colors.

Each of the following n - 1 lines contains two integers v_i and u_i (1 ≤ v_i, u_i ≤ n) — numbers of the squares connected by the corresponding road.

It's guaranteed, that it's possible to go from any square to any other square, moreover there is exactly one such simple path.

Output

Print "Yes" if it is possible to assign tile colors this way and "No" otherwise.

In case your answer is "Yes", print n integers from 1 to k each, the color of the tile for every square.

Examples

Input


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


Output


Yes
1 1 2 3 4 1 1


Input


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


Output


No

Note

The following pictures illustrate the pedestrian zone in first and second examples. The second picture also shows one possible distribution of colors among the squares for k = 4.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n positive integers a_1, a_2, ..., a_{n}.

For every a_{i} you need to find a positive integer k_{i} such that the decimal notation of 2^{k}_{i} contains the decimal notation of a_{i} as a substring among its last min(100, length(2^{k}_{i})) digits. Here length(m) is the length of the decimal notation of m.

Note that you don't have to minimize k_{i}. The decimal notations in this problem do not contain leading zeros.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 2 000) — the number of integers a_{i}.

Each of the next n lines contains a positive integer a_{i} (1 ≤ a_{i} < 10^11).


-----Output-----

Print n lines. The i-th of them should contain a positive integer k_{i} such that the last min(100, length(2^{k}_{i})) digits of 2^{k}_{i} contain the decimal notation of a_{i} as a substring. Integers k_{i} must satisfy 1 ≤ k_{i} ≤ 10^50.

It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.


-----Examples-----
Input
2
8
2

Output
3
1

Input
2
3
4857

Output
5
20

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Acacius is studying strings theory. Today he came with the following problem.

You are given a string s of length n consisting of lowercase English letters and question marks. It is possible to replace question marks with lowercase English letters in such a way that a string "abacaba" occurs as a substring in a resulting string exactly once?

Each question mark should be replaced with exactly one lowercase English letter. For example, string "a?b?c" can be transformed into strings "aabbc" and "azbzc", but can't be transformed into strings "aabc", "a?bbc" and "babbc".

Occurrence of a string t of length m in the string s of length n as a substring is a index i (1 ≤ i ≤ n - m + 1) such that string s[i..i+m-1] consisting of m consecutive symbols of s starting from i-th equals to string t. For example string "ababa" has two occurrences of a string "aba" as a substring with i = 1 and i = 3, but there are no occurrences of a string "aba" in the string "acba" as a substring.

Please help Acacius to check if it is possible to replace all question marks with lowercase English letters in such a way that a string "abacaba" occurs as a substring in a resulting string exactly once.

Input

First line of input contains an integer T (1 ≤ T ≤ 5000), number of test cases. T pairs of lines with test case descriptions follow.

The first line of a test case description contains a single integer n (7 ≤ n ≤ 50), length of a string s.

The second line of a test case description contains string s of length n consisting of lowercase English letters and question marks.

Output

For each test case output an answer for it.

In case if there is no way to replace question marks in string s with a lowercase English letters in such a way that there is exactly one occurrence of a string "abacaba" in the resulting string as a substring output "No".

Otherwise output "Yes" and in the next line output a resulting string consisting of n lowercase English letters. If there are multiple possible strings, output any.

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

Example

Input


6
7
abacaba
7
???????
11
aba?abacaba
11
abacaba?aba
15
asdf???f???qwer
11
abacabacaba


Output


Yes
abacaba
Yes
abacaba
Yes
abadabacaba
Yes
abacabadaba
No
No

Note

In first example there is exactly one occurrence of a string "abacaba" in the string "abacaba" as a substring.

In second example seven question marks can be replaced with any seven lowercase English letters and with "abacaba" in particular.

In sixth example there are two occurrences of a string "abacaba" as a substring.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The evil mastermind, Moriarty, strikes again!  He sent Sherlock an image of a wall, with N integers painted on it. Sherlock is asked to solve the puzzle and find the next clue.
Sherlock knows that Moriarty is a deceitful person. All the numbers painted on the wall are not valid. Only the numbers that are Coprime with the integer X are valid, and the rest are a deceit. Help Sherlock find the valid integers from the given array A so that he can track down Moriarty.  

Input:
First line contains T. T test cases follow.
First line of each test case contains two space-separated integers N and X.
Second line of each test case contains N space-separated integers, forming the array A. 

Output:
Print the valid integers separated by spaces in the order that they appear in the list or "-1" (without the quotes) if there are no valid integers, in a new line for each test case.  

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10^4
2 ≤ Ai, X ≤ 10^7

SAMPLE INPUT
1
5 4
2 5 8 3 13

SAMPLE OUTPUT
5 3 13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On her way to programming school tiger Dasha faced her first test — a huge staircase! [Image] 

The steps were numbered from one to infinity. As we know, tigers are very fond of all striped things, it is possible that it has something to do with their color. So on some interval of her way she calculated two values — the number of steps with even and odd numbers. 

You need to check whether there is an interval of steps from the l-th to the r-th (1 ≤ l ≤ r), for which values that Dasha has found are correct.


-----Input-----

In the only line you are given two integers a, b (0 ≤ a, b ≤ 100) — the number of even and odd steps, accordingly.


-----Output-----

In the only line print "YES", if the interval of steps described above exists, and "NO" otherwise.


-----Examples-----
Input
2 3

Output
YES

Input
3 1

Output
NO



-----Note-----

In the first example one of suitable intervals is from 1 to 5. The interval contains two even steps — 2 and 4, and three odd: 1, 3 and 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya takes part in the orienteering competition. There are n checkpoints located along the line at coordinates x_1, x_2, ..., x_{n}. Vasya starts at the point with coordinate a. His goal is to visit at least n - 1 checkpoint in order to finish the competition. Participant are allowed to visit checkpoints in arbitrary order.

Vasya wants to pick such checkpoints and the order of visiting them that the total distance travelled is minimized. He asks you to calculate this minimum possible value.


-----Input-----

The first line of the input contains two integers n and a (1 ≤ n ≤ 100 000,  - 1 000 000 ≤ a ≤ 1 000 000) — the number of checkpoints and Vasya's starting position respectively.

The second line contains n integers x_1, x_2, ..., x_{n} ( - 1 000 000 ≤ x_{i} ≤ 1 000 000) — coordinates of the checkpoints.


-----Output-----

Print one integer — the minimum distance Vasya has to travel in order to visit at least n - 1 checkpoint.


-----Examples-----
Input
3 10
1 7 12

Output
7

Input
2 0
11 -10

Output
10

Input
5 0
0 0 1000 0 0

Output
0



-----Note-----

In the first sample Vasya has to visit at least two checkpoints. The optimal way to achieve this is the walk to the third checkpoints (distance is 12 - 10 = 2) and then proceed to the second one (distance is 12 - 7 = 5). The total distance is equal to 2 + 5 = 7.

In the second sample it's enough to visit only one checkpoint so Vasya should just walk to the point  - 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N tiles are arranged in a row from left to right. The initial color of each tile is represented by a string S of length N.
The i-th tile from the left is painted black if the i-th character of S is 0, and painted white if that character is 1.
You want to repaint some of the tiles black or white, so that any two adjacent tiles have different colors.
At least how many tiles need to be repainted to satisfy the condition?

-----Constraints-----
 - 1 \leq |S| \leq 10^5
 - S_i is 0 or 1.

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

-----Output-----
Print the minimum number of tiles that need to be repainted to satisfy the condition.

-----Sample Input-----
000

-----Sample Output-----
1

The condition can be satisfied by repainting the middle tile white.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers and a number K. Find the count of distinct elements in every window of size K in the array.
Example 1:
Input:
N = 7, K = 4
A[] = {1,2,1,3,4,2,3}
Output: 3 4 4 3
Explanation: Window 1 of size k = 4 is
1 2 1 3. Number of distinct elements in
this window are 3. 
Window 2 of size k = 4 is 2 1 3 4. Number
of distinct elements in this window are 4.
Window 3 of size k = 4 is 1 3 4 2. Number
of distinct elements in this window are 4.
Window 4 of size k = 4 is 3 4 2 3. Number
of distinct elements in this window are 3.
Example 2:
Input:
N = 3, K = 2
A[] = {4,1,1}
Output: 2 1
Your Task:
Your task is to complete the function countDistinct() which takes the array A[], the size of the array(N) and the window size(K) as inputs and returns an array containing the count of distinct elements in every contiguous window of size K in the array A[].
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= K <= N <= 10^{5}
1 <= A[i] <= 10^{5 }, for each valid i

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Egor is a huge movie fan. He likes watching different kinds of movies: from drama movies to comedy movies, from teen movies to horror movies. He is planning to visit cinema this weekend, but he's not sure which movie he should watch.
There are n movies to watch during this weekend. Each movie can be characterized by two integers Li and Ri, denoting the length and the rating of the corresponding movie. Egor wants to watch exactly one movie with the maximal value of Li × Ri. If there are several such movies, he would pick a one with the maximal Ri among them. If there is still a tie, he would pick the one with the minimal index among them.
Your task is to help Egor to pick a movie to watch during this weekend.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases.
The first line of the test case description contains an integer n.
The second line of the test case description contains n integers L1, L2, ...,Ln. The following line contains n integers R1, R2, ..., Rn.

-----Output-----
For each test case, output a single integer i denoting the index of the movie that Egor should watch during this weekend. Note that we follow 1-based indexing.

-----Constraints-----
- 1 ≤ T ≤ 5
- 1 ≤ n ≤ 100
- 1 ≤ Li, Ri ≤ 100

-----Example-----
Input:
2
2
1 2
2 1
4
2 1 4 1
2 4 1 4

Output:
1
2

-----Explanation-----
In the first example case, both films have the same value of L × R, but the first film has a better rating.
In the second example case, the second and the fourth movies are equally good, but the second movie has a smaller index.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's denote that some array $b$ is bad if it contains a subarray $b_l, b_{l+1}, \dots, b_{r}$ of odd length more than $1$ ($l < r$ and $r - l + 1$ is odd) such that $\forall i \in \{0, 1, \dots, r - l\}$ $b_{l + i} = b_{r - i}$.

If an array is not bad, it is good.

Now you are given an array $a_1, a_2, \dots, a_n$. Some elements are replaced by $-1$. Calculate the number of good arrays you can obtain by replacing each $-1$ with some integer from $1$ to $k$.

Since the answer can be large, print it modulo $998244353$.


-----Input-----

The first line contains two integers $n$ and $k$ ($2 \le n, k \le 2 \cdot 10^5$) — the length of array $a$ and the size of "alphabet", i. e., the upper bound on the numbers you may use to replace $-1$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($a_i = -1$ or $1 \le a_i \le k$) — the array $a$.


-----Output-----

Print one integer — the number of good arrays you can get, modulo $998244353$.


-----Examples-----
Input
2 3
-1 -1

Output
9

Input
5 2
1 -1 -1 1 2

Output
0

Input
5 3
1 -1 -1 1 2

Output
2

Input
4 200000
-1 -1 12345 -1

Output
735945883

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
People in Chefland have three different eye colors, namely brown, blue, and green. green is the rarest of the eye colors whereas brown is most common.

The eye color of the child of two people is most likely to be the most common eye color between them. 

You are given two characters denoting the eye colors of two people in Chefland. The character R denotes bRown color, B denotes Blue color, and G denotes Green color.

Determine the most likely eye color of their child. (Print R, B or G denoting bRown, Blue or Green respectively).

Please see the sample test cases below for explained examples.

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

- The first (and only) line of input contains two space-separated characters, the eye colors of the parents.

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

Print a single character denoting the most likely eye color of the child. (Print R, B or G denoting brown, blue or green respectively).

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

- The input contains two space-separated characters
- Each character in the input is one among {R, B, G}.

------ subtasks ------ 

----- Sample Input 1 ------ 
R B

----- Sample Output 1 ------ 
R
----- explanation 1 ------ 
The two people have brown and blue eyes and brown is the most common. Therefore, their child  will most likely have brown eyes.

----- Sample Input 2 ------ 
B B

----- Sample Output 2 ------ 
B
----- explanation 2 ------ 
Both parents have blue eyes, therefore their child will most likely have blue eyes

----- Sample Input 3 ------ 
G B

----- Sample Output 3 ------ 
B
----- explanation 3 ------ 
The parents have green and blue eyes, out of which blue is more common than green, therefore the child will most likely have blue eyes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
My friend John and I are members of the "Fat to Fit Club (FFC)". John is worried because
each month a list with the weights of members is published and each month he is the last on the list
which means he is the heaviest. 

I am the one who establishes the list so I told him:
"Don't worry any more, I will modify the order of the list".
It was decided to attribute a "weight" to numbers. The weight of a number will be from now on
the sum of its digits. 

For example `99` will have "weight" `18`, `100` will have "weight"
`1` so in the list `100` will come before `99`.
Given a string with the weights of FFC members in normal order can you give this string ordered by "weights" of these numbers?

# Example:

`"56 65 74 100 99 68 86 180 90"` ordered by numbers weights becomes: 
`"100 180 90 56 65 74 68 86 99"`

When two numbers have the same "weight", let us class them as if they were strings (alphabetical ordering) and not numbers:
`100` is before `180` because its "weight" (1) is less than the one of `180` (9)
and `180` is before `90` since, having the same "weight" (9),  it comes before as a *string*.

All numbers in the list are positive numbers and the list can be empty.

# Notes

- it may happen that the input string have leading, trailing whitespaces and more than a unique whitespace between two consecutive numbers
- Don't modify the input
- For C: The result is freed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Autonomous Car Manufacturer (ACM) needs to design algorithms to control their cars. One particular problem is lane switching—if the car needs to switch lanes, it wants to do so in the safest manner.

Initially the car is in the leftmost lane, and the car needs to switch to the rightmost lane. The car has a variety of sensors and can obtain the locations of all cars in a section of the highway. When the car needs to switch lanes, it takes a snapshot of the sensor readings and design a plan to switch lanes based on the snapshot. The sensors have limited range. All sensor readings will be distances from the start of the sensor range. For safety reason, the areas outside of the sensor range are assumed to be occupied by cars.

You may assume that all other cars are travelling at exactly the speed limit. However, the ACM would like to set itself apart by producing cars that may drive at any speed regardless of the speed limit, as long as it does not hit any other car. For safety reasons, a lane switch is always done while driving at the speed limit.

When a lane switch occurs, the destination must have unoccupied space for the car to move into (a perfect fit is allowed). We define the safety factor of the plan as the closest distance to any car while executing the plan. We are only concerned about cars in the same lane, and will ignore distances between cars in different lanes. Obviously, the ACM wants its cars to choose a plan that has the highest safety factor.

The first sample input is illustrated below.

-----Input-----
The first line of input contains three integers $N$ ($2 \leq N \leq 100$), $M$ ($M \geq 1$), $R$ ($1 \leq R \leq 1000000$) indicating the number of lanes, the number of cars on the road, and the sensor range. The next $M$ lines describe each car with three integers: the lane number (between 0 and $N-1$, inclusive), the length of the car (positive), and the distance from the start of the sensor range to the back of the car. The distance is non-negative and at most $R$. The first car given is the ACM car. Lane 0 is the leftmost lane, and lane $N-1$ is the rightmost lane.

There are at most 100 cars in each lane. No two cars will overlap although they may touch bumper-to-bumper.

-----Output-----
If the ACM car can switch from lane 0 to lane $N-1$, print a single number indicating the maximum achievable safety factor. Otherwise, print Impossible. Your answer will be considered correct if its absolute error does not exceed $10^{-5}$.

-----Examples-----
Sample Input:
4 5 100
0 10 10
1 10 5
1 20 35
2 2 18
2 40 50
Sample Output:
2.500000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are 10 problems in a contest. You know that the score of each problem is either 1 or 100 points.

Chef came to know the total score of a participant and he is wondering how many problems were actually solved by that participant.

Given the total score P of the participant, determine the number of problems solved by the participant. Print -1 in case the score is invalid.

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line containing a single integer P - denoting the number of points scored by the participant.

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

For each testcase, output the number of problems solved by the participant or -1 if the score is invalid.

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

$1 ≤ T ≤ 1000$
$0 ≤ P ≤ 1000$

----- Sample Input 1 ------ 
5
103
0
6
142
1000

----- Sample Output 1 ------ 
4
0
6
-1
10

----- explanation 1 ------ 
Test Case $1$: The participant has solved $4$ problems out of which $3$ problems are worth $1$ point each while $1$ problem is worth $100$ points.

Test Case $2$: Since participant's score is $0$, he solved $0$ problems.

Test Case $3$: The participant has solved $6$ problems out of which all the problems are worth $1$ point.

Test Case $4$: It is not possible to get a score of $142$.

Test Case $5$: The participant solved all the $10$ problems and score of all the problems is $100$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The king is left alone on the chessboard. In spite of this loneliness, he doesn't lose heart, because he has business of national importance. For example, he has to pay an official visit to square t. As the king is not in habit of wasting his time, he wants to get from his current position s to square t in the least number of moves. Help him to do this.

<image>

In one move the king can get to the square that has a common side or a common vertex with the square the king is currently in (generally there are 8 different squares he can move to).

Input

The first line contains the chessboard coordinates of square s, the second line — of square t.

Chessboard coordinates consist of two characters, the first one is a lowercase Latin letter (from a to h), the second one is a digit from 1 to 8.

Output

In the first line print n — minimum number of the king's moves. Then in n lines print the moves themselves. Each move is described with one of the 8: L, R, U, D, LU, LD, RU or RD. 

L, R, U, D stand respectively for moves left, right, up and down (according to the picture), and 2-letter combinations stand for diagonal moves. If the answer is not unique, print any of them. 

Examples

Input

a8
h1


Output

7
RD
RD
RD
RD
RD
RD
RD

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