vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: A Tide of Riverscape

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
"Time," Mino thinks aloud.

"What?"

"Time and tide wait for no man," explains Mino. "My name, taken from the river, always reminds me of this."

"And what are you recording?"

"You see it, tide. Everything has its own period, and I think I've figured out this one," says Mino with confidence.

Doubtfully, Kanno peeks at Mino's records. 

The records are expressed as a string $s$ of characters '0', '1' and '.', where '0' denotes a low tide, '1' denotes a high tide, and '.' denotes an unknown one (either high or low).

You are to help Mino determine whether it's possible that after replacing each '.' independently with '0' or '1', a given integer $p$ is not a period of the resulting string. In case the answer is yes, please also show such a replacement to Mino.

In this problem, a positive integer $p$ is considered a period of string $s$, if for all $1 \leq i \leq \lvert s \rvert - p$, the $i$-th and $(i + p)$-th characters of $s$ are the same. Here $\lvert s \rvert$ is the length of $s$.

Input Specification:
The first line contains two space-separated integers $n$ and $p$ ($1 \leq p \leq n \leq 2000$) — the length of the given string and the supposed period, respectively.

The second line contains a string $s$ of $n$ characters — Mino's records. $s$ only contains characters '0', '1' and '.', and contains at least one '.' character.

Output Specification:
Output one line — if it's possible that $p$ is not a period of the resulting string, output any one of such strings; otherwise output "No" (without quotes, you can print letters in any case (upper or lower)).

Demo Input:
['10 7\n1.0.1.0.1.\n', '10 6\n1.0.1.1000\n', '10 9\n1........1\n']

Demo Output:
['1000100010\n', '1001101000\n', 'No\n']

Note:
In the first example, $7$ is not a period of the resulting string because the $1$-st and $8$-th characters of it are different.

In the second example, $6$ is not a period of the resulting string because the $4$-th and $10$-th characters of it are different.

In the third example, $9$ is always a period because the only constraint that the first and last characters are the same is already satisfied.

Note that there are multiple acceptable answers for the first two examples, you can print any of them.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
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 Specification:
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 Specification:
Print one integer — the minimum distance Vasya has to travel in order to visit at least *n*<=-<=1 checkpoint.

Demo Input:
['3 10\n1 7 12\n', '2 0\n11 -10\n', '5 0\n0 0 1000 0 0\n']

Demo Output:
['7\n', '10\n', '0\n']

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.
The Dogeforces company has k employees. Each employee, except for lower-level employees, has at least 2 subordinates. Lower-level employees have no subordinates. Each employee, except for the head of the company, has exactly one direct supervisor. The head of the company is a direct or indirect supervisor of all employees. It is known that in Dogeforces, each supervisor receives a salary strictly more than all his subordinates.

The full structure of the company is a secret, but you know the number of lower-level employees and for each pair of lower-level employees, the salary of their common supervisor is known (if there are several such supervisors, then the supervisor with the minimum salary). You have to restore the structure of the company.

Input

The first line contains a single integer n (2 ≤ n ≤ 500) — the number of lower-level employees.

This is followed by n lines, where i-th line contains n integers a_{i,1}, a_{i,2}, ..., a_{i,n} (1 ≤ a_{i,j} ≤ 5000) — salary of the common supervisor of employees with numbers i and j. It is guaranteed that a_{i,j} = a_{j,i}. Note that a_{i,i} is equal to the salary of the i-th employee.

Output

In the first line, print a single integer k — the number of employees in the company.

In the second line, print k integers c_1, c_2, ..., c_k, where c_i is the salary of the employee with the number i.

In the third line, print a single integer r — the number of the employee who is the head of the company.

In the following k-1 lines, print two integers v and u (1 ≤ v, u ≤ k) — the number of the employee and his direct supervisor.

Note that the lower-level employees have numbers from 1 to n, and for the rest of the employees, you have to assign numbers from n+1 to k. If there are several correct company structures, you can print any of them.

Example

Input


3
2 5 7
5 1 7
7 7 4


Output


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

Note

One of the possible structures in the first example: <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Green and Black Tea

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Innokentiy likes tea very much and today he wants to drink exactly *n* cups of tea. He would be happy to drink more but he had exactly *n* tea bags, *a* of them are green and *b* are black.

Innokentiy doesn't like to drink the same tea (green or black) more than *k* times in a row. Your task is to determine the order of brewing tea bags so that Innokentiy will be able to drink *n* cups of tea, without drinking the same tea more than *k* times in a row, or to inform that it is impossible. Each tea bag has to be used exactly once.

Input Specification:
The first line contains four integers *n*, *k*, *a* and *b* (1<=≤<=*k*<=≤<=*n*<=≤<=105, 0<=≤<=*a*,<=*b*<=≤<=*n*) — the number of cups of tea Innokentiy wants to drink, the maximum number of cups of same tea he can drink in a row, the number of tea bags of green and black tea. It is guaranteed that *a*<=+<=*b*<==<=*n*.

Output Specification:
If it is impossible to drink *n* cups of tea, print "NO" (without quotes).

Otherwise, print the string of the length *n*, which consists of characters 'G' and 'B'. If some character equals 'G', then the corresponding cup of tea should be green. If some character equals 'B', then the corresponding cup of tea should be black.

If there are multiple answers, print any of them.

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

Demo Output:
['GBGBG\n', 'BBGBGBB', 'NO\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Young Mirko is a smart, but mischievous boy who often wanders around parks looking for new ideas. This time he’s come across pensioners playing the card game Belote. They’ve invited him to help them determine the total number of points in a game.

Each card can be uniquely determined by its number and suit. A set of four cards is called a hand. At the beginning of a game one suit that “trumps” any other is chosen, and it is called the dominant suit. The number of points in a game is equal to the sum of values of each card from each hand in the game. Mirko has noticed that the pensioners have played $N$ hands and that suit $B$ was the dominant suit.

The value of each card depends on its number and whether its suit is dominant, and is given in Table 1.

Number

Value 

Dominant

Not dominant

A

$11$

$11$

K

$4$

$4$

Q

$3$

$3$

J

$20$

$2$

T

$10$

$10$

9

$14$

$0$

8

$0$

$0$

7

$0$

$0$Table 1: Scores 

Write a programme that will determine and output the number of points in the game.

-----Input-----
The first line contains the number of hands $N$ ($1 \leq N \leq 100$) and the value of suit $B$ (S, H, D, C) from the task. Each of the following $4N$ lines contains the description of a card (the first character is the number of the $i$-th card (A, K, Q, J, T, 9, 8, 7), and the second is the suit (S, H, D, C)).

-----Output-----
The first and only line of output must contain the number of points from the task.

-----Examples-----
Sample Input:
2 S
TH
9C
KS
QS
JS
TD
AD
JH
Sample Output:
60

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rahul is a young chap who loves strings but simply hates mathematics. While his friend Ramesh is in love with mathematics but hates strings. So their teacher decided to take a test which combined both these topics so that neither of them gets a better hand over the other.

Their teacher gave both of them a single string. The string consists of digits from 0-9 only. Then their teacher asked them to divide the string into exactly K parts such that each part is not greater than a fixed value Z. Since there could be many such ways to divide the string their teacher asked them to divide in such a manner that maximized the final sum of all the K parts.

This question really baffled both of them. Since they are in trouble they ask your help in finding out the maximum sum.

If it is not possible to cut the string into K parts satisfying the given conditions print -1.

Input:

The first line contains T denoting the number of test cases. 
The first line of each test case contains 2 space separated integers K and Z that are the number of parts in which the string is to be cut and the value that each part should not exceed. The second line of each test case contains the string.

Output:

For each test case print the required answer.

Constraints:

1 ≤ T ≤10

1 ≤  K  ≤100

1 ≤ Z ≤10^9

1 ≤  length of string  ≤ 100
The string contains characters from [0-9] only

SAMPLE INPUT
2
1 6
30901
2 85
07565

SAMPLE OUTPUT
-1
140

Explanation

For the first test case the only way to cut is to get the entire string that is 30901 but it's value is greater than 6 so -1.

For the second test case the optimal way is 075 and 65 which sum upto 140.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree consisting of n nodes numbered from 1 to n. The weights of edges of the tree can be any binary integer satisfying following Q conditions.

- 
		Each condition is of form u, v, x where u, v are nodes of the tree and x is a binary number. 

		For satisfying this condition,  sum of the weight of all the edges present in the path from node u to v of the tree, should have even if x = 0, odd otherwise. 
	

Now, you have to find out number of ways of assigning 0/1 (binary) weights to the edges of the tree satisfying the above conditions.
As the answer could be quite large, print your answer modulo 109 + 7.

-----Input-----
- The first line of input contains a single integer T denoting number of test cases.
- For each test case:
	
- First line contains two space separated integers n, Q.
- Each of the next n - 1 lines will contain two space separated integer  u, v denoting that there is an edge between vertex u and v in the tree.
- Each of the next Q lines will contain three space separated integer  u, v, x denoting a condition as stated in the probelm.

-----Output-----
- For each test case, output a single integer corresponding to the answer of the problem.

-----Constraints-----
- 1 ≤ u, v ≤ n
- 0 ≤ x ≤ 1

-----Subtasks-----
Subtask #1 : (10 points)
- Sum of each of variables n and Q over all the test cases ≤ 20

Subtask #2 : (20 points)
- Sum of each of variables n and Q over all the test cases ≤ 100

Subtask #3 : (30 points)
- Sum of each of variables n and Q over all the test cases ≤ 5000

Subtask #4 : (40 points)
- Sum of each of variables n and Q over all the test cases ≤ 100000

-----Example-----
Input:
3
3 2
1 2
1 3
1 2 0
1 3 0
3 0
1 2
2 3
3 1
1 2
2 3
1 2 1

Output:
1
4
2

-----Explanation-----
In the first example, 
You can only set the weight of each edge equal to 0 for satisfying the given condition. So, there is exactly one way of doing this. Hence answer is 1.

In the second example, 
There are two edges and there is no condition on the edges. So, you can assign them in 4 ways. 

In the third example, 
You have to assign the weight of edge between node 1 and 2 to 1. You can assign the remaining edge from 2 to 3 either 0 or 1. So, the answer is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbours of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighboors if they share one edge.
Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.
Binary matrix is a matrix with all cells equal to 0 or 1 only.
Zero matrix is a matrix with all cells equal to 0.
 
Example 1:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

Example 2:
Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We don't need to change it.

Example 3:
Input: mat = [[1,1,1],[1,0,1],[0,0,0]]
Output: 6

Example 4:
Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix can't be a zero matrix

 
Constraints:

m == mat.length
n == mat[0].length
1 <= m <= 3
1 <= n <= 3
mat[i][j] is 0 or 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day a bear lived on the Oxy axis. He was afraid of the dark, so he couldn't move at night along the plane points that aren't lit. One day the bear wanted to have a night walk from his house at point (l, 0) to his friend's house at point (r, 0), along the segment of length (r - l). Of course, if he wants to make this walk, he needs each point of the segment to be lit. That's why the bear called his friend (and yes, in the middle of the night) asking for a very delicate favor.

The Oxy axis contains n floodlights. Floodlight i is at point (xi, yi) and can light any angle of the plane as large as ai degree with vertex at point (xi, yi). The bear asked his friend to turn the floodlights so that he (the bear) could go as far away from his house as possible during the walking along the segment. His kind friend agreed to fulfill his request. And while he is at it, the bear wonders: what is the furthest he can go away from his house? Hep him and find this distance.

Consider that the plane has no obstacles and no other light sources besides the floodlights. The bear's friend cannot turn the floodlights during the bear's walk. Assume that after all the floodlights are turned in the correct direction, the bear goes for a walk and his friend goes to bed.

Input

The first line contains three space-separated integers n, l, r (1 ≤ n ≤ 20; - 105 ≤ l ≤ r ≤ 105). The i-th of the next n lines contain three space-separated integers xi, yi, ai ( - 1000 ≤ xi ≤ 1000; 1 ≤ yi ≤ 1000; 1 ≤ ai ≤ 90) — the floodlights' description. 

Note that two floodlights can be at the same point of the plane.

Output

Print a single real number — the answer to the problem. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

Examples

Input

2 3 5
3 1 45
5 1 45


Output

2.000000000


Input

1 0 1
1 1 30


Output

0.732050808


Input

1 0 1
1 1 45


Output

1.000000000


Input

1 0 2
0 2 90


Output

2.000000000

Note

In the first sample, one of the possible solutions is: 

<image>

In the second sample, a single solution is: 

<image>

In the third sample, a single solution is: 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A game field is a strip of 1 × n square cells. In some cells there are Packmen, in some cells — asterisks, other cells are empty.

Packman can move to neighboring cell in 1 time unit. If there is an asterisk in the target cell then Packman eats it. Packman doesn't spend any time to eat an asterisk.

In the initial moment of time all Packmen begin to move. Each Packman can change direction of its move unlimited number of times, but it is not allowed to go beyond the boundaries of the game field. Packmen do not interfere with the movement of other packmen; in one cell there can be any number of packmen moving in any directions.

Your task is to determine minimum possible time after which Packmen can eat all the asterisks.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^5) — the length of the game field.

The second line contains the description of the game field consisting of n symbols. If there is symbol '.' in position i — the cell i is empty. If there is symbol '*' in position i — in the cell i contains an asterisk. If there is symbol 'P' in position i — Packman is in the cell i.

It is guaranteed that on the game field there is at least one Packman and at least one asterisk.


-----Output-----

Print minimum possible time after which Packmen can eat all asterisks.


-----Examples-----
Input
7
*..P*P*

Output
3

Input
10
.**PP.*P.*

Output
2



-----Note-----

In the first example Packman in position 4 will move to the left and will eat asterisk in position 1. He will spend 3 time units on it. During the same 3 time units Packman in position 6 will eat both of neighboring with it asterisks. For example, it can move to the left and eat asterisk in position 5 (in 1 time unit) and then move from the position 5 to the right and eat asterisk in the position 7 (in 2 time units). So in 3 time units Packmen will eat all asterisks on the game field.

In the second example Packman in the position 4 will move to the left and after 2 time units will eat asterisks in positions 3 and 2. Packmen in positions 5 and 8 will move to the right and in 2 time units will eat asterisks in positions 7 and 10, respectively. So 2 time units is enough for Packmen to eat all asterisks on the game field.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

One day Petya encountered a tree with *n* vertexes. Besides, the tree was weighted, i. e. each edge of the tree has weight (a positive integer). An edge is lucky if its weight is a lucky number. Note that a tree with *n* vertexes is an undirected connected graph that has exactly *n*<=-<=1 edges.

Petya wondered how many vertex triples (*i*,<=*j*,<=*k*) exists that on the way from *i* to *j*, as well as on the way from *i* to *k* there must be at least one lucky edge (all three vertexes are pairwise distinct). The order of numbers in the triple matters, that is, the triple (1,<=2,<=3) is not equal to the triple (2,<=1,<=3) and is not equal to the triple (1,<=3,<=2). 

Find how many such triples of vertexes exist.

Input Specification:
The first line contains the single integer *n* (1<=≤<=*n*<=≤<=105) — the number of tree vertexes. Next *n*<=-<=1 lines contain three integers each: *u**i* *v**i* *w**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*,<=1<=≤<=*w**i*<=≤<=109) — the pair of vertexes connected by the edge and the edge's weight.

Output Specification:
On the single line print the single number — the answer.

Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is recommended to use the cin, cout streams or the %I64d specificator.

Demo Input:
['4\n1 2 4\n3 1 2\n1 4 7\n', '4\n1 2 4\n1 3 47\n1 4 7447\n']

Demo Output:
['16\n', '24\n']

Note:
The 16 triples of vertexes from the first sample are: (1, 2, 4), (1, 4, 2), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2).

In the second sample all the triples should be counted: 4·3·2 = 24.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You work in the best consumer electronics corporation, and your boss wants to find out which three products generate the most revenue.
Given 3 lists of the same length like these:

* products: `["Computer", "Cell Phones", "Vacuum Cleaner"]`
* amounts: `[3, 24, 8]`
* prices: `[199, 299, 399]`


return the three product names with the highest revenue (`amount * price`).

**Note**: if multiple products have the same revenue, order them according to their original positions in the input list.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a heavy rainfall over the Antique Cultural Museum, and the roof has sprung a leak! All the beautiful paintings risk destruction, if it weren’t for one brave night watchman standing in the water’s way – Klunkas Plaskocek.

To protect all of the paintings, Klunkas has brought $N$ buckets and placed them in a long row to catch the water falling from the ceiling. Each bucket can hold exactly $K$ drops of water. If a drop falls into a bucket which is full, the water drop will overflow to the bucket standing to the left. If that bucket is full as well, the drop will keep flowing left until there is a non-full bucket.

Klunkas needs your help to prevent the leftmost bucket overflowing. After every drop of water falls, Klunkas wants to know which bucket it ended up in, so that he can keep track of the water levels of the buckets.

Due to the very regular nature of rain, Klunkas figured that the $R$ rain drops fall in a very nice pattern. Given constants $X_0, A, B$, we define the sequence $X_ i$ as\[ X_ i = (A \cdot X_{i-1} + B) \mod N \]

The bucket which the $i$-th rain drop falls into, is then $X_ i$ for $i = 1, \dots , R$. The leftmost bucket has the number $0$, and the rightmost bucket has the number $N-1$.

-----Input-----
Input consists of the space-separated integers $1 \le N \le 10^6$, $1 \le R \le 10^7$, $1 \le K \le 10$, $0 \le X_0, A, B \le 2^{31} - 1$.

-----Output-----
If the leftmost bucket overflows, output “OVERFLOW”.

Otherwise, the output should be calculated as follows:

Let $O_ i$ be the bucket which the $i$:th rain drop ended up in, and let $a = 0$.

Then, for every $i$ from $1$ to $R$, set $a := (53 \cdot a + O_ i) \mod 199933$.

The output should then be a line with the integer $a$.

-----Examples-----
Sample Input 1:
10 6 1 2 1 8
Sample Output 1:
OVERFLOW

Sample Input 2:
10 6 1 4 1 8
Sample Output 2:
79732

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