vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Divisor is the Conquerer is a solitaire card game. Although this simple game itself is a great way to pass one’s time, you, a programmer, always kill your time by programming. Your task is to write a computer program that automatically solves Divisor is the Conquerer games. Here is the rule of this game:

First, you randomly draw N cards (1 ≤ N ≤ 52) from your deck of playing cards. The game is played only with those cards; the other cards will not be used.

Then you repeatedly pick one card to play among those in your hand. You are allowed to choose any card in the initial turn. After that, you are only allowed to pick a card that conquers the cards you have already played. A card is said to conquer a set of cards when the rank of the card divides the sum of the ranks in the set. For example, the card 7 conquers the set {5, 11, 12}, while the card 11 does not conquer the set {5, 7, 12}.

You win the game if you successfully play all N cards you have drawn. You lose if you fails, that is, you faces a situation in which no card in your hand conquers the set of cards you have played.



Input

The input consists of multiple test cases.

Each test case consists of two lines. The first line contains an integer N (1 ≤ N ≤ 52), which represents the number of the cards. The second line contains N integers c1 , . . . , cN (1 ≤ ci ≤ 13), each of which represents the rank of the card. You may assume that there are at most four cards with the same rank in one list.

The input is terminated by a line with a single zero.

Output

For each test case, you should output one line. If there are any winning strategies for the cards of the input, print any one of them as a list of N integers separated by a space.

If there is no winning strategy, print “No”.

Example

Input

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


Output

3 3 1 7 2
No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Lucky Numbers (easy)

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not.

One day Petya came across a positive integer *n*. Help him to find the least super lucky number which is not less than *n*.

Input Specification:
The only line contains a positive integer *n* (1<=≤<=*n*<=≤<=109). This number doesn't have leading zeroes.

Output Specification:
Output the least super lucky number that is more than or equal to *n*.

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

Demo Input:
['4500\n', '47\n']

Demo Output:
['4747\n', '47\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a permutation of 1,2,...,N: p_1,p_2,...,p_N. Determine if the state where p_i=i for every i can be reached by performing the following operation any number of times:
 - Choose three elements p_{i-1},p_{i},p_{i+1} (2\leq i\leq N-1) such that p_{i-1}>p_{i}>p_{i+1} and reverse the order of these three.

-----Constraints-----
 - 3 \leq N \leq 3 × 10^5
 - p_1,p_2,...,p_N is a permutation of 1,2,...,N.

-----Input-----
Input is given from Standard Input in the following format:
N
p_1
:
p_N

-----Output-----
If the state where p_i=i for every i can be reached by performing the operation, print Yes; otherwise, print No.

-----Sample Input-----
5
5
2
1
4
3

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

The state where p_i=i for every i can be reached as follows:
 - Reverse the order of p_1,p_2,p_3. The sequence p becomes 1,2,5,4,3.
 - Reverse the order of p_3,p_4,p_5. The sequence p becomes 1,2,3,4,5.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dima loves making pictures on a piece of squared paper. And yet more than that Dima loves the pictures that depict one of his favorite figures. 

A piece of squared paper of size *n*<=×<=*m* is represented by a table, consisting of *n* rows and *m* columns. All squares are white on blank squared paper. Dima defines a picture as an image on a blank piece of paper, obtained by painting some squares black.

The picture portrays one of Dima's favorite figures, if the following conditions hold:
 -  The picture contains at least one painted cell; -  All painted cells form a connected set, that is, you can get from any painted cell to any other one (you can move from one cell to a side-adjacent one); -  The minimum number of moves needed to go from the painted cell at coordinates (*x*1,<=*y*1) to the painted cell at coordinates (*x*2,<=*y*2), moving only through the colored cells, equals |*x*1<=-<=*x*2|<=+<=|*y*1<=-<=*y*2|. 
Now Dima is wondering: how many paintings are on an *n*<=×<=*m* piece of paper, that depict one of his favorite figures? Count this number modulo 1000000007 (109<=+<=7).

Input Specification:
The first line contains two integers *n* and *m* — the sizes of the piece of paper (1<=≤<=*n*,<=*m*<=≤<=150).

Output Specification:
In a single line print the remainder after dividing the answer to the problem by number 1000000007 (109<=+<=7).

Demo Input:
['2 2\n', '3 4\n']

Demo Output:
['13\n', '571\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There will be a launch of a new, powerful and unusual collider very soon, which located along a straight line. *n* particles will be launched inside it. All of them are located in a straight line and there can not be two or more particles located in the same point. The coordinates of the particles coincide with the distance in meters from the center of the collider, *x**i* is the coordinate of the *i*-th particle and its position in the collider at the same time. All coordinates of particle positions are even integers.

You know the direction of each particle movement — it will move to the right or to the left after the collider's launch start. All particles begin to move simultaneously at the time of the collider's launch start. Each particle will move straight to the left or straight to the right with the constant speed of 1 meter per microsecond. The collider is big enough so particles can not leave it in the foreseeable time.

Write the program which finds the moment of the first collision of any two particles of the collider. In other words, find the number of microseconds before the first moment when any two particles are at the same point.

Input Specification:
The first line contains the positive integer *n* (1<=≤<=*n*<=≤<=200<=000) — the number of particles. 

The second line contains *n* symbols "L" and "R". If the *i*-th symbol equals "L", then the *i*-th particle will move to the left, otherwise the *i*-th symbol equals "R" and the *i*-th particle will move to the right.

The third line contains the sequence of pairwise distinct even integers *x*1,<=*x*2,<=...,<=*x**n* (0<=≤<=*x**i*<=≤<=109) — the coordinates of particles in the order from the left to the right. It is guaranteed that the coordinates of particles are given in the increasing order.

Output Specification:
In the first line print the only integer — the first moment (in microseconds) when two particles are at the same point and there will be an explosion. 

Print the only integer -1, if the collision of particles doesn't happen.

Demo Input:
['4\nRLRL\n2 4 6 10\n', '3\nLLR\n40 50 60\n']

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

Note:
In the first sample case the first explosion will happen in 1 microsecond because the particles number 1 and 2 will simultaneously be at the same point with the coordinate 3. 

In the second sample case there will be no explosion because there are no particles which will simultaneously be at the same point.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N squares arranged in a row.
The squares are numbered 1, 2, ..., N, from left to right.
Snuke is painting each square in red, green or blue.
According to his aesthetic sense, the following M conditions must all be satisfied.
The i-th condition is:
 - There are exactly x_i different colors among squares l_i, l_i + 1, ..., r_i.
In how many ways can the squares be painted to satisfy all the conditions?
Find the count modulo 10^9+7.

-----Constraints-----
 - 1 ≤ N ≤ 300
 - 1 ≤ M ≤ 300
 - 1 ≤ l_i ≤ r_i ≤ N
 - 1 ≤ x_i ≤ 3

-----Input-----
Input is given from Standard Input in the following format:
N M
l_1 r_1 x_1
l_2 r_2 x_2
:
l_M r_M x_M

-----Output-----
Print the number of ways to paint the squares to satisfy all the conditions, modulo 10^9+7.

-----Sample Input-----
3 1
1 3 3

-----Sample Output-----
6

The six ways are:
 - RGB
 - RBG
 - GRB
 - GBR
 - BRG
 - BGR
where R, G and B correspond to red, green and blue squares, respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Taisia has $n$ six-sided dice. Each face of the die is marked with a number from $1$ to $6$, each number from $1$ to $6$ is used once.

Taisia rolls all $n$ dice at the same time and gets a sequence of values $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 6$), where $a_i$ is the value on the upper face of the $i$-th dice. The sum of this sequence is equal to $s$.

Suddenly, Taisia's pet cat steals exactly one dice with maximum value $a_i$ and calculates the sum of the values on the remaining $n-1$ dice, which is equal to $r$.

You only know the number of dice $n$ and the values of $s$, $r$. Restore a possible sequence $a$ that fulfills the constraints.


-----Input-----

The first line contains the integer $t$ ($1 \le t \le 1000$) — the number of testcases.

Each testcase is given on a separate line and contains three integers $n$, $s$, $r$ ($2 \le n \le 50$, $1 \le r < s \le 300$).

It is guaranteed that a solution exists.


-----Output-----

For each testcase, print: $n$ integers $a_1, a_2, \ldots, a_n$ in any order. It is guaranteed that such sequence exists.

If there are multiple solutions, print any.


-----Examples-----

Input
7
2 2 1
2 4 2
4 9 5
5 17 11
3 15 10
4 4 3
5 20 15
Output
1 1
2 2 
1 2 2 4
6 4 2 3 2
5 5 5
1 1 1 1
1 4 5 5 5


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today RK has a special task for you. RK gives you a positive integer N. First you have to find all the sequences of length N consisting of characters 'O' and 'Z' only such that no two 'Z' are adjacent in any sequence. After finding all such sequences you have to find Kth sequence when all found sequences are sorted lexicographically in ascending order. If no Kth sequence exist then print -1.

Input :
The first line contains the number of test cases T. Each test case consists of two positive integers N and K.

Output :
For each test case output Kth sequence or -1 if Kth sequence does not exist.

Constraint : 
1 ≤ T ≤ 100
1 ≤ N ≤ 10^3
1 ≤ K ≤ 10^17

SAMPLE INPUT
1
3 2

SAMPLE OUTPUT
OOZ

Explanation

For sample, all valid sequences in lexicographic ascending order are :
OOO, OOZ, OZO, ZOO, ZOZ
2nd sequence in this order is OOZ.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to solve some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

-----Sample Input:-----
3
2
3
4

-----Sample Output:-----
0
*1
**2
0
*1
**2
***3
0
*1
**2
***3
****4

-----EXPLANATION:-----
No need, else pattern can be decode easily.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set of points $x_1$, $x_2$, ..., $x_n$ on the number line.

Two points $i$ and $j$ can be matched with each other if the following conditions hold:  neither $i$ nor $j$ is matched with any other point;  $|x_i - x_j| \ge z$. 

What is the maximum number of pairs of points you can match with each other?


-----Input-----

The first line contains two integers $n$ and $z$ ($2 \le n \le 2 \cdot 10^5$, $1 \le z \le 10^9$) — the number of points and the constraint on the distance between matched points, respectively.

The second line contains $n$ integers $x_1$, $x_2$, ..., $x_n$ ($1 \le x_i \le 10^9$).


-----Output-----

Print one integer — the maximum number of pairs of points you can match with each other.


-----Examples-----
Input
4 2
1 3 3 7

Output
2

Input
5 5
10 9 5 8 7

Output
1



-----Note-----

In the first example, you may match point $1$ with point $2$ ($|3 - 1| \ge 2$), and point $3$ with point $4$ ($|7 - 3| \ge 2$).

In the second example, you may match point $1$ with point $3$ ($|5 - 10| \ge 5$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan is a student at Berland State University (BSU). There are n days in Berland week, and each of these days Ivan might have some classes at the university.

There are m working hours during each Berland day, and each lesson at the university lasts exactly one hour. If at some day Ivan's first lesson is during i-th hour, and last lesson is during j-th hour, then he spends j - i + 1 hours in the university during this day. If there are no lessons during some day, then Ivan stays at home and therefore spends 0 hours in the university.

Ivan doesn't like to spend a lot of time in the university, so he has decided to skip some lessons. He cannot skip more than k lessons during the week. After deciding which lessons he should skip and which he should attend, every day Ivan will enter the university right before the start of the first lesson he does not skip, and leave it after the end of the last lesson he decides to attend. If Ivan skips all lessons during some day, he doesn't go to the university that day at all.

Given n, m, k and Ivan's timetable, can you determine the minimum number of hours he has to spend in the university during one week, if he cannot skip more than k lessons?


-----Input-----

The first line contains three integers n, m and k (1 ≤ n, m ≤ 500, 0 ≤ k ≤ 500) — the number of days in the Berland week, the number of working hours during each day, and the number of lessons Ivan can skip, respectively.

Then n lines follow, i-th line containing a binary string of m characters. If j-th character in i-th line is 1, then Ivan has a lesson on i-th day during j-th hour (if it is 0, there is no such lesson).


-----Output-----

Print the minimum number of hours Ivan has to spend in the university during the week if he skips not more than k lessons.


-----Examples-----
Input
2 5 1
01001
10110

Output
5

Input
2 5 0
01001
10110

Output
8



-----Note-----

In the first example Ivan can skip any of two lessons during the first day, so he spends 1 hour during the first day and 4 hours during the second day.

In the second example Ivan can't skip any lessons, so he spends 4 hours every day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Chefland, precipitation is measured using a rain gauge in millimetre per hour. 

Chef categorises rainfall as:
LIGHT, if rainfall is less than 3 millimetre per hour.
MODERATE, if rainfall is greater than equal to 3 millimetre per hour and less than 7 millimetre per hour.
HEAVY if rainfall is greater than equal to 7 millimetre per hour.

Given that it rains at X millimetre per hour on a day, find whether the rain is LIGHT, MODERATE, or HEAVY.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single integer X — the rate of rainfall in millimetre per hour. 

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

For each test case, output on a new line, whether the rain is LIGHT, MODERATE, or HEAVY.

You may print each character in lowercase or uppercase. For example, LIGHT, light, Light, and liGHT, are all identical.

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

$1 ≤ T ≤ 20$
$1 ≤ X ≤ 20$

----- Sample Input 1 ------ 
4
1
20
3
7

----- Sample Output 1 ------ 
LIGHT
HEAVY
MODERATE
HEAVY
----- explanation 1 ------ 
Test case $1$: The rate of precipitation is less than $3$. Thus, the rain is LIGHT.

Test case $2$: The rate of precipitation is greater than equal to $7$. Thus, the rain is HEAVY.

Test case $3$: The rate of precipitation is greater than equal to $3$ and less than $7$. Thus, the rain is MODERATE.

Test case $4$: The rate of precipitation is greater than equal to $7$. Thus, the rain is HEAVY.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The airline company NCPC Airways has flights to and from $n$ cities, numbered from 1 to $n$, around the entire world. However, they only have $n - 1$ different flights (operating in both directions), so in order to travel between any two cities you might have to take several flights. In fact, since the management has made sure that it’s possible to travel between any pair of cities, there is exactly one set of flights a passenger have to take in order to travel between two cities (assuming you want to use the same airline).

Recently many of NCPC Airways frequent flyers have complained that they have had to change flights too often to get to their final destination. Since NCPC Airways doesn’t want to loose their customers to other airline companies, but still keep the nice property of their flights, they have decided to cancel one of their current flights and replace it with another flight. Help the company by writing a program which finds the best flight to cancel and the best new flight to add so that the maximum number of flight changes a passenger might have to make when travelling between any pair of cities in which NCPC Airways operates is minimized.

The input will be constructed so that it is always possible to improve the maximum number of flight changes needed.

-----Input-----
The first line in the input contains the integer $n$ ($4 \leq n \leq 2500$), the number of cities NCPC Airways operates in. Then follow $n - 1$ lines specifying the flights. Each flight is given as a pair of cities $a$ and $b$ ($1 \le a, b \le n$).

-----Output-----
The output should consist of three lines. The first line should contain an integer, the minimum number of flights needed to take when travelling between any pair of cities after changing one of the flights. The second line should contain two integers, specifying the two cities between which the flight should be canceled. The third line should contain two integers, specifying the two cities where a new flight should be added.

If there are more than one optimal solution, any one of them will be accepted.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a skier (marked below by the `X`). You have made it to the Olympics! Well done.

```
\_\_\_X\_
\*\*\*\*\*\
\*\*\*\*\*\*\
\*\*\*\*\*\*\*\
\*\*\*\*\*\*\*\*\
\*\*\*\*\*\*\*\*\*\\.\_\_\_\_/
```

Your job in this kata is to calculate the maximum speed you will achieve during your downhill run. The speed is dictated by the height of the mountain. Each element of the array is a layer of the mountain as indicated by the diagram above (and further below). So for this example the mountain has a height of 5 (5 rows of stars). `Speed` is `mountain height * 1.5`.

The jump length is calculated by `(mountain height * speed * 9) / 10`. Jump length should be rounded to 2 decimal places.

You must return the length of the resulting jump as a string in the following format:

* when less than 10 m: `"X metres: He's crap!"`
* between 10 and 25 m: `"X metres: He's ok!"`
* between 25 and 50 m: `"X metres: He's flying!"`
* when more than 50 m: `"X metres: Gold!!"`

So in the example case above, the right answer would be `"33.75 metres: He's flying!"`

Sadly, it takes a lot of time to make arrays look like mountains, so the tests wont all look so nice. To give an example, the above mountain would look as follows in most cases:

```
[*****, ******, *******, ********, *********]
```
Not as much fun, eh?

*p.s. if you think "metre" is incorrect, please [read this](https://en.wikipedia.org/wiki/Metre#Spelling)*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers A and B.
Print a grid where each square is painted white or black that satisfies the following conditions, in the format specified in Output section:
 - Let the size of the grid be h \times w (h vertical, w horizontal). Both h and w are at most 100.
 - The set of the squares painted white is divided into exactly A connected components.
 - The set of the squares painted black is divided into exactly B connected components.
It can be proved that there always exist one or more solutions under the conditions specified in Constraints section.
If there are multiple solutions, any of them may be printed.

-----Notes-----
Two squares painted white, c_1 and c_2, are called connected when the square c_2 can be reached from the square c_1 passing only white squares by repeatedly moving up, down, left or right to an adjacent square.
A set of squares painted white, S, forms a connected component when the following conditions are met:
 - Any two squares in S are connected.
 - No pair of a square painted white that is not included in S and a square included in S is connected.
A connected component of squares painted black is defined similarly.

-----Constraints-----
 - 1 \leq A \leq 500
 - 1 \leq B \leq 500

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Output should be in the following format:
 - In the first line, print integers h and w representing the size of the grid you constructed, with a space in between.
 - Then, print h more lines. The i-th (1 \leq i \leq h) of these lines should contain a string s_i as follows:
 - If the square at the i-th row and j-th column (1 \leq j \leq w) in the grid is painted white, the j-th character in s_i should be ..
 - If the square at the i-th row and j-th column (1 \leq j \leq w) in the grid is painted black, the j-th character in s_i should be #.

-----Sample Input-----
2 3

-----Sample Output-----
3 3
##.
..#
#.#

This output corresponds to the grid below:

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