vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A boy Petya loves chess very much. He even came up with a chess piece of his own, a semiknight. The semiknight can move in any of these four directions: 2 squares forward and 2 squares to the right, 2 squares forward and 2 squares to the left, 2 squares backward and 2 to the right and 2 squares backward and 2 to the left. Naturally, the semiknight cannot move beyond the limits of the chessboard.

Petya put two semiknights on a standard chessboard. Petya simultaneously moves with both semiknights. The squares are rather large, so after some move the semiknights can meet, that is, they can end up in the same square. After the meeting the semiknights can move on, so it is possible that they meet again. Petya wonders if there is such sequence of moves when the semiknights meet. Petya considers some squares bad. That is, they do not suit for the meeting. The semiknights can move through these squares but their meetings in these squares don't count.

Petya prepared multiple chess boards. Help Petya find out whether the semiknights can meet on some good square for each board.

Please see the test case analysis.


-----Input-----

The first line contains number t (1 ≤ t ≤ 50) — the number of boards. Each board is described by a matrix of characters, consisting of 8 rows and 8 columns. The matrix consists of characters ".", "#", "K", representing an empty good square, a bad square and the semiknight's position, correspondingly. It is guaranteed that matrix contains exactly 2 semiknights. The semiknight's squares are considered good for the meeting. The tests are separated by empty line.


-----Output-----

For each test, print on a single line the answer to the problem: "YES", if the semiknights can meet and "NO" otherwise.


-----Examples-----
Input
2
........
........
......#.
K..##..#
.......#
...##..#
......#.
K.......

........
........
..#.....
..#..#..
..####..
...##...
........
....K#K#

Output
YES
NO



-----Note-----

Consider the first board from the sample. We will assume the rows and columns of the matrix to be numbered 1 through 8 from top to bottom and from left to right, correspondingly. The knights can meet, for example, in square (2, 7). The semiknight from square (4, 1) goes to square (2, 3) and the semiknight goes from square (8, 1) to square (6, 3). Then both semiknights go to (4, 5) but this square is bad, so they move together to square (2, 7).

On the second board the semiknights will never meet.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mad scientist Mike has applied for a job. His task is to manage a system of water pumping stations.

The system consists of n pumping stations, which are numbered by integers from 1 to n. Some pairs of stations are connected by bidirectional pipes through which water can flow in either direction (but only in one at a time). For each pipe you know its bandwidth — the maximum number of liters of water that can flow through it in one hour. Each pumping station can pump incoming water from some stations to other stations through the pipes, provided that in one hour the total influx of water to the station is equal to the total outflux of water from the station.

It is Mike's responsibility to pump water between stations. From station a to station b through the pipes (possibly through other stations) within one hour one can transmit a certain number of liters of water according to the rules described above. During this time, water from other stations can not flow into station a, and can not flow out of the station b. However, any amount of water can flow out of station a or in station b. If a total of x litres of water flows out of the station a in an hour, then Mike gets x bollars more to his salary.

To get paid, Mike needs to work for n - 1 days, according to the contract. On the first day he selects two stations v1 and v2, and within one hour he pumps a certain amount of water from v1 to v2. Next, on the i-th day Mike chooses a station vi + 1 that has been never selected before, and pumps a certain amount of water out of the station vi to station vi + 1 for one hour. The quantity of water he pumps on the i-th day does not depend on the amount of water pumped on the (i - 1)-th day.

Mike needs to earn as much bollars as he can for his projects. Help Mike find such a permutation of station numbers v1, v2, ..., vn so Mike will be able to earn the highest possible salary.

Input

The first line of the input contains two space-separated integers n and m (2 ≤ n ≤ 200, 1 ≤ m ≤ 1000) — the number of stations and pipes in the system, accordingly. The i-th of the next m lines contains three space-separated integers ai, bi and ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 100) — the numbers of stations connected by the i-th pipe and the pipe's bandwidth, accordingly. It is guaranteed that any two stations are connected by at most one pipe and that there is a pipe path between any two stations.

Output

On the first line print a single integer — the maximum salary Mike can earn.

On the second line print a space-separated permutation of n numbers from 1 to n — the numbers of stations in the sequence v1, v2, ..., vn. If there are multiple answers, print any of them.

Examples

Input

6 11
1 2 10
1 6 8
2 3 4
2 5 2
2 6 3
3 4 5
3 5 4
3 6 2
4 5 7
4 6 2
5 6 3


Output

77
6 2 1 5 3 4 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is the size of the input.

You are given a string $s$ consisting of $n$ characters, each character is 'R', 'G' or 'B'.

You are also given an integer $k$. Your task is to change the minimum number of characters in the initial string $s$ so that after the changes there will be a string of length $k$ that is a substring of $s$, and is also a substring of the infinite string "RGBRGBRGB ...".

A string $a$ is a substring of string $b$ if there exists a positive integer $i$ such that $a_1 = b_i$, $a_2 = b_{i + 1}$, $a_3 = b_{i + 2}$, ..., $a_{|a|} = b_{i + |a| - 1}$. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 2000$) — the number of queries. Then $q$ queries follow.

The first line of the query contains two integers $n$ and $k$ ($1 \le k \le n \le 2000$) — the length of the string $s$ and the length of the substring.

The second line of the query contains a string $s$ consisting of $n$ characters 'R', 'G' and 'B'.

It is guaranteed that the sum of $n$ over all queries does not exceed $2000$ ($\sum n \le 2000$).


-----Output-----

For each query print one integer — the minimum number of characters you need to change in the initial string $s$ so that after changing there will be a substring of length $k$ in $s$ that is also a substring of the infinite string "RGBRGBRGB ...".


-----Example-----
Input
3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

Output
1
0
3



-----Note-----

In the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".

In the second example, the substring is "BRG".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you know, all the kids in Berland love playing with cubes. Little Petya has n towers consisting of cubes of the same size. Tower with number i consists of a_{i} cubes stacked one on top of the other. Petya defines the instability of a set of towers as a value equal to the difference between the heights of the highest and the lowest of the towers. For example, if Petya built five cube towers with heights (8, 3, 2, 6, 3), the instability of this set is equal to 6 (the highest tower has height 8, the lowest one has height 2). 

The boy wants the instability of his set of towers to be as low as possible. All he can do is to perform the following operation several times: take the top cube from some tower and put it on top of some other tower of his set. Please note that Petya would never put the cube on the same tower from which it was removed because he thinks it's a waste of time. 

Before going to school, the boy will have time to perform no more than k such operations. Petya does not want to be late for class, so you have to help him accomplish this task.


-----Input-----

The first line contains two space-separated positive integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1000) — the number of towers in the given set and the maximum number of operations Petya can perform. The second line contains n space-separated positive integers a_{i} (1 ≤ a_{i} ≤ 10^4) — the towers' initial heights.


-----Output-----

In the first line print two space-separated non-negative integers s and m (m ≤ k). The first number is the value of the minimum possible instability that can be obtained after performing at most k operations, the second number is the number of operations needed for that.

In the next m lines print the description of each operation as two positive integers i and j, each of them lies within limits from 1 to n. They represent that Petya took the top cube from the i-th tower and put in on the j-th one (i ≠ j). Note that in the process of performing operations the heights of some towers can become equal to zero.

If there are multiple correct sequences at which the minimum possible instability is achieved, you are allowed to print any of them.


-----Examples-----
Input
3 2
5 8 5

Output
0 2
2 1
2 3

Input
3 4
2 2 4

Output
1 1
3 2

Input
5 3
8 3 2 6 3

Output
3 3
1 3
1 2
1 3



-----Note-----

In the first sample you need to move the cubes two times, from the second tower to the third one and from the second one to the first one. Then the heights of the towers are all the same and equal to 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Little Elephant and Magic Square

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Elephant loves magic squares very much.

A magic square is a 3<=×<=3 table, each cell contains some positive integer. At that the sums of integers in all rows, columns and diagonals of the table are equal. The figure below shows the magic square, the sum of integers in all its rows, columns and diagonals equals 15.

The Little Elephant remembered one magic square. He started writing this square on a piece of paper, but as he wrote, he forgot all three elements of the main diagonal of the magic square. Fortunately, the Little Elephant clearly remembered that all elements of the magic square did not exceed 105. 

Help the Little Elephant, restore the original magic square, given the Elephant's notes.

Input Specification:
The first three lines of the input contain the Little Elephant's notes. The first line contains elements of the first row of the magic square. The second line contains the elements of the second row, the third line is for the third row. The main diagonal elements that have been forgotten by the Elephant are represented by zeroes.

It is guaranteed that the notes contain exactly three zeroes and they are all located on the main diagonal. It is guaranteed that all positive numbers in the table do not exceed 105.

Output Specification:
Print three lines, in each line print three integers — the Little Elephant's magic square. If there are multiple magic squares, you are allowed to print any of them. Note that all numbers you print must be positive and not exceed 105.

It is guaranteed that there exists at least one magic square that meets the conditions.

Demo Input:
['0 1 1\n1 0 1\n1 1 0\n', '0 3 6\n5 0 5\n4 7 0\n']

Demo Output:
['1 1 1\n1 1 1\n1 1 1\n', '6 3 6\n5 5 5\n4 7 4\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n clocks in the Pradnya Planet which beep after different time periods.
The clocks are represented as C1, C2, ... Cn and their respective time periods 
by T1, T2, T3, ... Tn.
Each clock beeps with the intensity of 1. If k clocks beep at the same time, it 
is counted as one beep of intensity k.
There are p aliens in the pradnya world who are sleeping at time t=0.
These p aliens are denoted by A1, A2, ... Ap.
All the aliens are insomniac but all in a different way. 
An alien wakes up at time t, either if the number of beeps completed before or at the time t exceeds a particular value(Beep Value), or if the intensity of any beep before or at time t exceeds a particular value(Intensity Value).
Now, the aliens go to their "Big Boss" with a time t.
The "Big Boss" then tells whether the alien will wake up till that time t.
Since the queries(q) of the aliens are too large, help the "Big Boss" to answer the queries.

Note: A clock Ci with time period Ti beeps at time: Ti, 2Ti, 3Ti, ... so on.

Input Format:
The first line contains an integer n denoting the number of clocks.

The next line contains n space separated integers denoting the time periods of the n respective clocks.

The next line contains p denoting the number of aliens.

The next p lines contain two space separated integers b and i, denoting the Beep Value and Intensity Value of the respective aliens

The next line contains q denoting the number of queries.

The next q lines contain two space separated integers in and t, denoting the alien  Ain and the time t respectively.

Output Format:
For each of the q lines, output "Awake" if the alien Ain will awake before time t, 
else output "Asleep", if the alien does not wake up before time t. 

Constraints:
1 ≤ n ≤ 10^5
1 ≤ time period of any clock ≤ 10^3
1 ≤ p ≤ 10^3
1 ≤ q ≤ 10^5
1 ≤ i ≤ n
1 ≤ t ≤ 10^5
1 ≤ b ≤ tSAMPLE INPUT
3
1 2 3
3
3 3
3 1
4 2
3
1 3
2 3
3 2

SAMPLE OUTPUT
Asleep
Awake
Asleep

Explanation

At time t = 1, no of beeps = 1 and maximum intensity value is 1

At time t=2, no of beeps = 2 and maximum intensity value is 2

At time t=3, no of beeps = 3 and maximum intensity value is 3.

For the 1st query, the alien A1 will be asleep at t=3, because the no of  beeps(3) do not exceed 3 and maximum intensity does not exceed 3.

For the 2nd query, the alien A2 will wake up at t=3, because the maximum intensity(2) exceeds 1.

For the 3rd query, the alien A3 will be asleep at t=2, because the no of beeps(2) do not exceed 4 and maximum intensity(2) does not exceed 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Elements of Harmony are six supernatural artifacts representing subjective aspects of harmony. They are arguably the most powerful force in Equestria. The inside of Elements of Harmony can be seen as a complete graph with n vertices labeled from 0 to n - 1, where n is a power of two, equal to 2m.

<image>

The energy in Elements of Harmony is in constant movement. According to the ancient book, the energy of vertex u in time i (ei[u]) equals to: 

<image>

Here b[] is the transformation coefficient — an array of m + 1 integers and f(u, v) is the number of ones in the binary representation of number (u xor v).

Given the transformation coefficient and the energy distribution at time 0 (e0[]). Help Twilight Sparkle predict the energy distribution at time t (et[]). The answer can be quite large, so output it modulo p.

Input

The first line contains three integers m, t and p (1 ≤ m ≤ 20; 0 ≤ t ≤ 1018; 2 ≤ p ≤ 109). The following line contains n (n = 2m) integers e0[i] (1 ≤ e0[i] ≤ 109; 0 ≤ i < n). The next line contains m + 1 integers b[i] (0 ≤ b[i] ≤ 109; 0 ≤ i ≤ m).

Output

Output n lines, the i-th line must contain a single integer et[i] modulo p.

Examples

Input

2 2 10000
4 1 2 3
0 1 0


Output

14
6
6
14

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi is meeting up with Aoki.
They have planned to meet at a place that is D meters away from Takahashi's house in T minutes from now.
Takahashi will leave his house now and go straight to the place at a speed of S meters per minute.
Will he arrive in time?

-----Constraints-----
 - 1 \leq D \leq 10000
 - 1 \leq T \leq 10000
 - 1 \leq S \leq 10000
 - All values in input are integers.

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

-----Output-----
If Takahashi will reach the place in time, print Yes; otherwise, print No.

-----Sample Input-----
1000 15 80

-----Sample Output-----
Yes

It takes 12.5 minutes to go 1000 meters to the place at a speed of 80 meters per minute. They have planned to meet in 15 minutes so he will arrive in time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alex just got a new hula hoop, he loves it but feels discouraged because his little brother is better than him

Write a program where Alex can input (n) how many times the hoop goes round and it will return him an encouraging message :) 

-If Alex gets 10 or more hoops, return the string "Great, now move on to tricks".

-If he doesn't get 10 hoops, return the string "Keep at it until you get it".

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

Time Limit: 3 seconds

Memory Limit: 128 megabytes

Problem Description:
*n* fish, numbered from 1 to *n*, live in a lake. Every day right one pair of fish meet, and the probability of each other pair meeting is the same. If two fish with indexes i and j meet, the first will eat up the second with the probability *a**ij*, and the second will eat up the first with the probability *a**ji*<==<=1<=-<=*a**ij*. The described process goes on until there are at least two fish in the lake. For each fish find out the probability that it will survive to be the last in the lake.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=18) — the amount of fish in the lake. Then there follow *n* lines with *n* real numbers each — matrix *a*. *a**ij* (0<=≤<=*a**ij*<=≤<=1) — the probability that fish with index *i* eats up fish with index *j*. It's guaranteed that the main diagonal contains zeros only, and for other elements the following is true: *a**ij*<==<=1<=-<=*a**ji*. All real numbers are given with not more than 6 characters after the decimal point.

Output Specification:
Output *n* space-separated real numbers accurate to not less than 6 decimal places. Number with index *i* should be equal to the probability that fish with index *i* will survive to be the last in the lake.

Demo Input:
['2\n0 0.5\n0.5 0\n', '5\n0 1 1 1 1\n0 0 0.5 0.5 0.5\n0 0.5 0 0.5 0.5\n0 0.5 0.5 0 0.5\n0 0.5 0.5 0.5 0\n']

Demo Output:
['0.500000 0.500000 ', '1.000000 0.000000 0.000000 0.000000 0.000000 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After the festive opening of your new store, the Boutique store for Alternative Paramedicine and Cwakhsahlvereigh, to your disappointment you find out that you are not making as many sales as you had hoped. To remedy this, you decide to run a special offer: you will mark some subset of the $n$ items for sale in your store as participating in the offer, and if people buy exactly two of these items, and the cost of these items is strictly more than $X$ euros, you will give them a free complimentary unicorn horn!

Since you recently found out all your unicorn horns are really narwhal tusks, you decide to rig the offer by picking the participating items in such a way that no one can earn a horn anyway.

To make sure no one becomes suspicious, you want to mark as many items as possible as participating in the offer.

-----Input-----
 - On the first line are two integers, $1 \leq n \leq 10^5$, the number of items for sale in your store, and $1\leq X \leq 10^9$, the minimum cost specified in the statement.
 - On the second line are $n$ positive integers, each at most $10^9$. These are the prices of the items in the store.

-----Output-----
Print the maximum number of items you can mark as part of your special offer, without anyone actually being able to receive a horn.

-----Examples-----
Sample Input 1:
5 6
1 2 3 4 5
Sample Output 1:
3

Sample Input 2:
5 10
4 8 1 9 7
Sample Output 2:
2

Sample Input 3:
4 10
1 3 1 7
Sample Output 3:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: King's Problem?

Time Limit: 3 seconds

Memory Limit: 256 megabytes

Problem Description:
Every true king during his life must conquer the world, hold the Codeforces world finals, win pink panda in the shooting gallery and travel all over his kingdom.

King Copa has already done the first three things. Now he just needs to travel all over the kingdom. The kingdom is an infinite plane with Cartesian coordinate system on it. Every city is a point on this plane. There are *n* cities in the kingdom at points with coordinates (*x*1,<=0),<=(*x*2,<=0),<=...,<=(*x**n*,<=0), and there is one city at point (*x**n*<=+<=1,<=*y**n*<=+<=1). 

King starts his journey in the city number *k*. Your task is to find such route for the king, which visits all cities (in any order) and has minimum possible length. It is allowed to visit a city twice. The king can end his journey in any city. Between any pair of cities there is a direct road with length equal to the distance between the corresponding points. No two cities may be located at the same point.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=105,<=1<=≤<=*k*<=≤<=*n*<=+<=1) — amount of cities and index of the starting city. The second line contains *n*<=+<=1 numbers *x**i*. The third line contains *y**n*<=+<=1. All coordinates are integers and do not exceed 106 by absolute value. No two cities coincide.

Output Specification:
Output the minimum possible length of the journey. Your answer must have relative or absolute error less than 10<=-<=6.

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

Demo Output:
['3.41421356237309490000', '3.82842712474619030000', '14.24264068711928400000']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In order to establish dominance amongst his friends, Chef has decided that he will only walk in large steps of length exactly $K$ feet. However, this has presented many problems in Chef’s life because there are certain distances that he cannot traverse. Eg. If his step length is $5$ feet, he cannot travel a distance of $12$ feet. Chef has a strict travel plan that he follows on most days, but now he is worried that some of those distances may become impossible to travel. Given $N$ distances, tell Chef which ones he cannot travel.

-----Input:-----
- The first line will contain a single integer $T$, the number of test cases.
- The first line of each test case will contain two space separated integers - $N$, the number of distances, and $K$, Chef’s step length.
- The second line of each test case will contain $N$ space separated integers, the $i^{th}$ of which represents $D_i$, the distance of the $i^{th}$ path.

-----Output:-----
For each testcase, output a string consisting of $N$ characters. The $i^{th}$ character should be $1$ if the distance is traversable, and $0$ if not. 

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 1000$
- $1 \leq K \leq 10^9$
- $1 \leq D_i \leq 10^9$

-----Subtasks-----
- 100 points : No additional constraints.

-----Sample Input:-----
1
5 3
12 13 18 20 27216

-----Sample Output:-----
10101

-----Explanation:-----
The first distance can be traversed in $4$ steps.

The second distance cannot be traversed.

The third distance can be traversed in $6$ steps.

The fourth distance cannot be traversed.

The fifth distance can be traversed in $9072$ steps.

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