vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Bash's Big Day

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bash has set out on a journey to become the greatest Pokemon master. To get his first Pokemon, he went to Professor Zulu's Lab. Since Bash is Professor Zulu's favourite student, Zulu allows him to take as many Pokemon from his lab as he pleases.

But Zulu warns him that a group of *k*<=&gt;<=1 Pokemon with strengths {*s*1,<=*s*2,<=*s*3,<=...,<=*s**k*} tend to fight among each other if *gcd*(*s*1,<=*s*2,<=*s*3,<=...,<=*s**k*)<==<=1 (see notes for *gcd* definition).

Bash, being smart, does not want his Pokemon to fight among each other. However, he also wants to maximize the number of Pokemon he takes from the lab. Can you help Bash find out the maximum number of Pokemon he can take? 

Note: A Pokemon cannot fight with itself.

Input Specification:
The input consists of two lines.

The first line contains an integer *n* (1<=≤<=*n*<=≤<=105), the number of Pokemon in the lab.

The next line contains *n* space separated integers, where the *i*-th of them denotes *s**i* (1<=≤<=*s**i*<=≤<=105), the strength of the *i*-th Pokemon.

Output Specification:
Print single integer — the maximum number of Pokemons Bash can take.

Demo Input:
['3\n2 3 4\n', '5\n2 3 4 6 7\n']

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

Note:
*gcd* (greatest common divisor) of positive integers set {*a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>} is the maximum positive integer that divides all the integers {*a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>}.

In the first sample, we can take Pokemons with strengths {2, 4} since *gcd*(2, 4) = 2.

In the second sample, we can take Pokemons with strengths {2, 4, 6}, and there is no larger group with *gcd* ≠ 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array Arr of size N, print all its elements.
Example 1:
Input:
N = 5
Arr[] = {1, 2, 3, 4, 5}
Output: 1 2 3 4 5
Example 2:
Input:
N = 4
Arr[] = {2, 3, 5, 5}
Output: 2 3 5 5
Your Task:
Complete the function printArray() which takes an array arr, single integer n, as input parameters and prints the value of the array space separated.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= Arr[i] <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is a great fan of television.

He wrote down all the TV programs he is interested in for today. His list contains n shows, i-th of them starts at moment l_{i} and ends at moment r_{i}.

Polycarp owns two TVs. He can watch two different shows simultaneously with two TVs but he can only watch one show at any given moment on a single TV. If one show ends at the same moment some other show starts then you can't watch them on a single TV.

Polycarp wants to check out all n shows. Are two TVs enough to do so?


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 2·10^5) — the number of shows.

Each of the next n lines contains two integers l_{i} and r_{i} (0 ≤ l_{i} < r_{i} ≤ 10^9) — starting and ending time of i-th show.


-----Output-----

If Polycarp is able to check out all the shows using only two TVs then print "YES" (without quotes). Otherwise, print "NO" (without quotes).


-----Examples-----
Input
3
1 2
2 3
4 5

Output
YES

Input
4
1 2
2 3
2 3
1 2

Output
NO

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day *n* students come to the stadium. They want to play football, and for that they need to split into teams, the teams must have an equal number of people.

We know that this group of people has archenemies. Each student has at most two archenemies. Besides, if student *A* is an archenemy to student *B*, then student *B* is an archenemy to student *A*.

The students want to split so as no two archenemies were in one team. If splitting in the required manner is impossible, some students will have to sit on the bench.

Determine the minimum number of students you will have to send to the bench in order to form the two teams in the described manner and begin the game at last.

Input Specification:
The first line contains two integers *n* and *m* (2<=≤<=*n*<=≤<=100, 1<=≤<=*m*<=≤<=100) — the number of students and the number of pairs of archenemies correspondingly.

Next *m* lines describe enmity between students. Each enmity is described as two numbers *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*, *a**i*<=≠<=*b**i*) — the indexes of the students who are enemies to each other. Each enmity occurs in the list exactly once. It is guaranteed that each student has no more than two archenemies.

You can consider the students indexed in some manner with distinct integers from 1 to *n*.

Output Specification:
Print a single integer — the minimum number of students you will have to send to the bench in order to start the game.

Demo Input:
['5 4\n1 2\n2 4\n5 3\n1 4\n', '6 2\n1 4\n3 4\n', '6 6\n1 2\n2 3\n3 1\n4 5\n5 6\n6 4\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monocarp had a tree which consisted of $n$ vertices and was rooted at vertex $1$. He decided to study BFS (Breadth-first search), so he ran BFS on his tree, starting from the root. BFS can be described by the following pseudocode:a = [] # the order in which vertices were processed

q = Queue()

q.put(1) # place the root at the end of the queue

while not q.empty():

    k = q.pop() # retrieve the first vertex from the queue

    a.append(k) # append k to the end of the sequence in which vertices were visited

    for y in g[k]: # g[k] is the list of all children of vertex k, sorted in ascending order

        q.put(y)



Monocarp was fascinated by BFS so much that, in the end, he lost his tree. Fortunately, he still has a sequence of vertices, in which order vertices were visited by the BFS algorithm (the array a from the pseudocode). Monocarp knows that each vertex was visited exactly once (since they were put and taken from the queue exactly once). Also, he knows that all children of each vertex were viewed in ascending order.

Monocarp knows that there are many trees (in the general case) with the same visiting order $a$, so he doesn't hope to restore his tree. Monocarp is okay with any tree that has minimum height.

The height of a tree is the maximum depth of the tree's vertices, and the depth of a vertex is the number of edges in the path from the root to it. For example, the depth of vertex $1$ is $0$, since it's the root, and the depth of all root's children are $1$.

Help Monocarp to find any tree with given visiting order $a$ and minimum height.


-----Input-----

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

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$; $a_i \neq a_j$; $a_1 = 1$) — the order in which the vertices were visited by the BFS algorithm.

It's guaranteed that the total sum of $n$ over test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case print the minimum possible height of a tree with the given visiting order $a$.


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

Output
3
1
1



-----Note-----

In the first test case, there is only one tree with the given visiting order:  [Image] 

In the second test case, there is only one tree with the given visiting order as well:  [Image] 

In the third test case, an optimal tree with the given visiting order is shown below:  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer `n`, return first n dgits of Thue-Morse sequence, as a string (see examples).

Thue-Morse sequence is a binary sequence with 0 as the first element. The rest of the sequece is obtained by adding the Boolean (binary) complement of a group obtained so far.

```
For example:

0
01
0110
01101001
and so on...
```

![alt](https://upload.wikimedia.org/wikipedia/commons/f/f1/Morse-Thue_sequence.gif)

Ex.:
```python
thue_morse(1);  #"0"
thue_morse(2);  #"01"
thue_morse(5);  #"01101"
thue_morse(10): #"0110100110"
```

- You don't need to test if n is valid - it will always be a positive integer.
- `n` will be between 1 and 10000

[Thue-Morse on Wikipedia](https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence)

[Another kata on Thue-Morse](https://www.codewars.com/kata/simple-fun-number-106-is-thue-morse) by @myjinxin2015

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
My name is James diGriz, I'm the most clever robber and treasure hunter in the whole galaxy. There are books written about my adventures and songs about my operations, though you were able to catch me up in a pretty awkward moment.

I was able to hide from cameras, outsmart all the guards and pass numerous traps, but when I finally reached the treasure box and opened it, I have accidentally started the clockwork bomb! Luckily, I have met such kind of bombs before and I know that the clockwork mechanism can be stopped by connecting contacts with wires on the control panel of the bomb in a certain manner.

I see n contacts connected by n - 1 wires. Contacts are numbered with integers from 1 to n. Bomb has a security mechanism that ensures the following condition: if there exist k ≥ 2 contacts c1, c2, ..., ck forming a circuit, i. e. there exist k distinct wires between contacts c1 and c2, c2 and c3, ..., ck and c1, then the bomb immediately explodes and my story ends here. In particular, if two contacts are connected by more than one wire they form a circuit of length 2. It is also prohibited to connect a contact with itself.

On the other hand, if I disconnect more than one wire (i. e. at some moment there will be no more than n - 2 wires in the scheme) then the other security check fails and the bomb also explodes. So, the only thing I can do is to unplug some wire and plug it into a new place ensuring the fact that no circuits appear.

I know how I should put the wires in order to stop the clockwork. But my time is running out! Help me get out of this alive: find the sequence of operations each of which consists of unplugging some wire and putting it into another place so that the bomb is defused. 

Input

The first line of the input contains n (2 ≤ n ≤ 500 000), the number of contacts.

Each of the following n - 1 lines contains two of integers xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi) denoting the contacts currently connected by the i-th wire.

The remaining n - 1 lines contain the description of the sought scheme in the same format.

It is guaranteed that the starting and the ending schemes are correct (i. e. do not contain cicuits nor wires connecting contact with itself).

Output

The first line should contain k (k ≥ 0) — the minimum number of moves of unplugging and plugging back some wire required to defuse the bomb.

In each of the following k lines output four integers ai, bi, ci, di meaning that on the i-th step it is neccesary to unplug the wire connecting the contacts ai and bi and plug it to the contacts ci and di. Of course the wire connecting contacts ai and bi should be present in the scheme.

If there is no correct sequence transforming the existing scheme into the sought one, output -1.

Examples

Input

3
1 2
2 3
1 3
3 2


Output

1
1 2 1 3


Input

4
1 2
2 3
3 4
2 4
4 1
1 3


Output

3
1 2 1 3
4 3 4 1
2 3 2 4

Note

Picture with the clarification for the sample tests:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are a lot of problems related to the shortest paths. Nevertheless, there are not much problems, related to the shortest paths in average.
Consider a directed graph G, consisting of N nodes and M edges. Consider a walk from the node A to the node B in this graph. The average length of this walk will be total sum of weight of its' edges divided by number of edges. Every edge counts as many times as it appears in this path.
Now, your problem is quite simple. For the given graph and two given nodes, find out the shortest average length of the walk between these nodes. Please note, that the length of the walk need not to be finite, but average walk length will be.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a pair of space-separated integers N and M denoting the number of nodes and the number of edges in the graph.
Each of the following M lines contains a triple of space-separated integers Xi Yi Zi, denoting the arc, connecting the node Xi to the node Yi (but not vice-versa!) having the weight of Zi.
The next line contains a pair of space separated integers A and B, denoting the first and the last node of the path.

-----Output-----
For each test case, output a single line containing the length of the shortest path in average.
If there is no path at all, output just -1 on the corresponding line of the output.

-----Constraints-----
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ 1000
- A is not equal to B
- 1 ≤ A, B, Xi, Yi ≤ N
- 1 ≤ Zi ≤ 100
- There are no self-loops and multiple edges in the graph.
- 1 ≤ sum of N over all test cases ≤ 10000
- 1 ≤ sum of M over all test cases ≤ 20000

-----Subtasks-----
- Subtask #1 (45 points): 1 ≤ N ≤ 10, 1 ≤ M ≤ 20; Your answer will be considered correct in case it has an absolute or relative error of no more than 10-2.
- Subtask #2 (55 points): no additional constraints; Your answer will be considered correct in case it has an absolute or relative error of no more than 10-6.

-----Example-----
Input:2
3 3
1 2 1
2 3 2
3 2 3
1 3
3 3
1 2 10
2 3 1
3 2 1
1 3

Output:1.5
1.0

-----Explanation-----
Example case 1. The walk 1 -> 2 and 2 -> 3 has average length of 3/2 = 1.5. Any other walks in the graph will have more or equal average length than this.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are many interesting tasks on domino tilings. For example, an interesting fact is known. Let us take a standard chessboard (8 × 8) and cut exactly two squares out of it. It turns out that the resulting board can always be tiled using dominoes 1 × 2, if the two cut out squares are of the same color, otherwise it is impossible. 

Petya grew bored with dominoes, that's why he took a chessboard (not necessarily 8 × 8), cut some squares out of it and tries to tile it using triminoes. Triminoes are reactangles 1 × 3 (or 3 × 1, because triminoes can be rotated freely), also the two extreme squares of a trimino are necessarily white and the square in the middle is black. The triminoes are allowed to put on the chessboard so that their squares matched the colors of the uncut squares of the chessboard, and also the colors must match: the black squares must be matched with the black ones only and the white ones — with the white squares. The triminoes must not protrude above the chessboard or overlap each other. All the uncut squares of the board must be covered with triminoes. 

Help Petya find out if it is possible to tile his board using triminos in the described way and print one of the variants of tiling.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) — the board size. Next n lines contain m symbols each and represent the board description. If some position contains ".", then the square in this position has been cut out. Symbol "w" stands for a white square, "b" stands for a black square. It is guaranteed that through adding the cut squares can result in a correct chessboard (i.e. with alternating black and white squares), thought, perhaps, of a non-standard size.

Output

If at least one correct tiling exists, in the first line print "YES" (without quotes), and then — the tiling description. The description must contain n lines, m symbols in each. The cut out squares, as well as in the input data, are marked by ".". To denote triminoes symbols "a", "b", "c", "d" can be used, and all the three squares of each trimino must be denoted by the same symbol. If two triminoes share a side, than they must be denoted by different symbols. Two triminoes not sharing a common side can be denoted by one and the same symbol (c.f. sample).

If there are multiple correct ways of tiling, it is allowed to print any. If it is impossible to tile the board using triminoes or the correct tiling, for which four symbols "a", "b", "c", "d" would be enough, doesn't exist, print "NO" (without quotes) in the first line.

Examples

Input

6 10
.w.wbw.wbw
wbwbw.w.w.
bw.wbwbwbw
w.wbw.wbwb
...wbw.w.w
..wbw.wbw.


Output

YES
.a.aaa.ccc
baccc.c.a.
ba.dddcbab
b.aaa.cbab
...bbb.b.b
..ccc.ddd.

Input

2 2
wb
bw


Output

NO


Input

1 3
wbw


Output

YES
bbb


Input

1 3
...


Output

YES
...

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Where Are My Flakes?

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
One morning the Cereal Guy found out that all his cereal flakes were gone. He found a note instead of them. It turned out that his smart roommate hid the flakes in one of *n* boxes. The boxes stand in one row, they are numbered from 1 to *n* from the left to the right. The roommate left hints like "Hidden to the left of the *i*-th box" ("To the left of *i*"), "Hidden to the right of the *i*-th box" ("To the right of *i*"). Such hints mean that there are no flakes in the *i*-th box as well. The Cereal Guy wants to know the minimal number of boxes he necessarily needs to check to find the flakes considering all the hints. Or he wants to find out that the hints are contradictory and the roommate lied to him, that is, no box has the flakes.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*<=≤<=1000,<=0<=≤<=*m*<=≤<=1000) which represent the number of boxes and the number of hints correspondingly. Next *m* lines contain hints like "To the left of *i*" and "To the right of *i*", where *i* is integer (1<=≤<=*i*<=≤<=*n*). The hints may coincide.

Output Specification:
The answer should contain exactly one integer — the number of boxes that should necessarily be checked or "-1" if the hints are contradictory.

Demo Input:
['2 1\nTo the left of 2\n', '3 2\nTo the right of 1\nTo the right of 2\n', '3 1\nTo the left of 3\n', '3 2\nTo the left of 2\nTo the right of 1\n']

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

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera is a coder. Recently he wrote a funny program. The pseudo code for this program is given below:

Now Valera wonders: given the values *x*, *k* and *p*, what is the expected value of the resulting number *s*?

Input Specification:
The first line of the input contains three integers *x*,<=*k*,<=*p* (1<=≤<=*x*<=≤<=109; 1<=≤<=*k*<=≤<=200; 0<=≤<=*p*<=≤<=100).

Output Specification:
Print the required expected value. Your answer will be considered correct if the absolute or relative error doesn't exceed 10<=-<=6.

Demo Input:
['1 1 50\n', '5 3 0\n', '5 3 25\n']

Demo Output:
['1.0000000000000\n', '3.0000000000000\n', '1.9218750000000\n']

Note:
If the concept of expected value is new to you, you can read about it by the link: 

http://en.wikipedia.org/wiki/Expected_value

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kevin Sun wants to move his precious collection of *n* cowbells from Naperthrill to Exeter, where there is actually grass instead of corn. Before moving, he must pack his cowbells into *k* boxes of a fixed size. In order to keep his collection safe during transportation, he won't place more than two cowbells into a single box. Since Kevin wishes to minimize expenses, he is curious about the smallest size box he can use to pack his entire collection. 

Kevin is a meticulous cowbell collector and knows that the size of his *i*-th (1<=≤<=*i*<=≤<=*n*) cowbell is an integer *s**i*. In fact, he keeps his cowbells sorted by size, so *s**i*<=-<=1<=≤<=*s**i* for any *i*<=&gt;<=1. Also an expert packer, Kevin can fit one or two cowbells into a box of size *s* if and only if the sum of their sizes does not exceed *s*. Given this information, help Kevin determine the smallest *s* for which it is possible to put all of his cowbells into *k* boxes of size *s*.

Input Specification:
The first line of the input contains two space-separated integers *n* and *k* (1<=≤<=*n*<=≤<=2·*k*<=≤<=100<=000), denoting the number of cowbells and the number of boxes, respectively.

The next line contains *n* space-separated integers *s*1,<=*s*2,<=...,<=*s**n* (1<=≤<=*s*1<=≤<=*s*2<=≤<=...<=≤<=*s**n*<=≤<=1<=000<=000), the sizes of Kevin's cowbells. It is guaranteed that the sizes *s**i* are given in non-decreasing order.

Output Specification:
Print a single integer, the smallest *s* for which it is possible for Kevin to put all of his cowbells into *k* boxes of size *s*.

Demo Input:
['2 1\n2 5\n', '4 3\n2 3 5 9\n', '3 2\n3 5 7\n']

Demo Output:
['7\n', '9\n', '8\n']

Note:
In the first sample, Kevin must pack his two cowbells into the same box. 

In the second sample, Kevin can pack together the following sets of cowbells: {2, 3}, {5} and {9}.

In the third sample, the optimal solution is {3, 5} and {7}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing a game where you have been sent in a town to collect 10 types of coin and their symbol are defined with $A, B, C, D, E, F, G, H , I, J$. In that town every enemy have a coin. By killing one you will get a coin from that enemy. Each enemy have only a unique coin.
The challange of the game is You have to collect all the coin and only then you will get the victory. You are a brave gamer so you took this hard challange and successfully finished it. After finishing, you are thinking of the game. You know the order off collecting coin. Now you are thinking how many enemy did you have killed?
Can you solve that out?

-----Input:-----
First line of the input is an integer $T$.Next T line consists of a string which denotes the order of your collecting coins. The string consists of Uppercase latin latter only and from A to J.

-----Output:-----
Print T line, in each line an integer with the number of enemy you have killed in the operation.

-----Constraints-----
- $1 \leq T \leq 5000$

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

-----Sample Output:-----
10

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