vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Niwel is a little golden bear. As everyone knows, bears live in forests, but Niwel got tired of seeing all the trees so he decided to move to the city.

In the city, Niwel took on a job managing bears to deliver goods. The city that he lives in can be represented as a directed graph with n nodes and m edges. Each edge has a weight capacity. A delivery consists of a bear carrying weights with their bear hands on a simple path from node 1 to node n. The total weight that travels across a particular edge must not exceed the weight capacity of that edge.

Niwel has exactly x bears. In the interest of fairness, no bear can rest, and the weight that each bear carries must be exactly the same. However, each bear may take different paths if they like.

Niwel would like to determine, what is the maximum amount of weight he can deliver (it's the sum of weights carried by bears). Find the maximum weight.


-----Input-----

The first line contains three integers n, m and x (2 ≤ n ≤ 50, 1 ≤ m ≤ 500, 1 ≤ x ≤ 100 000) — the number of nodes, the number of directed edges and the number of bears, respectively.

Each of the following m lines contains three integers a_{i}, b_{i} and c_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}, 1 ≤ c_{i} ≤ 1 000 000). This represents a directed edge from node a_{i} to b_{i} with weight capacity c_{i}. There are no self loops and no multiple edges from one city to the other city. More formally, for each i and j that i ≠ j it's guaranteed that a_{i} ≠ a_{j} or b_{i} ≠ b_{j}. It is also guaranteed that there is at least one path from node 1 to node n.


-----Output-----

Print one real value on a single line — the maximum amount of weight Niwel can deliver if he uses exactly x bears. Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


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

Output
1.5000000000

Input
5 11 23
1 2 3
2 3 4
3 4 5
4 5 6
1 3 4
2 4 5
3 5 6
1 4 2
2 5 3
1 5 2
3 2 30

Output
10.2222222222



-----Note-----

In the first sample, Niwel has three bears. Two bears can choose the path $1 \rightarrow 3 \rightarrow 4$, while one bear can choose the path $1 \rightarrow 2 \rightarrow 4$. Even though the bear that goes on the path $1 \rightarrow 2 \rightarrow 4$ can carry one unit of weight, in the interest of fairness, he is restricted to carry 0.5 units of weight. Thus, the total weight is 1.5 units overall. Note that even though Niwel can deliver more weight with just 2 bears, he must use exactly 3 bears on this day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Now it's time of Olympiads. Vanya and Egor decided to make his own team to take part in a programming Olympiad. They've been best friends ever since primary school and hopefully, that can somehow help them in teamwork.

For each team Olympiad, Vanya takes his play cards with numbers. He takes only the cards containing numbers 1 and 0. The boys are very superstitious. They think that they can do well at the Olympiad if they begin with laying all the cards in a row so that:  there wouldn't be a pair of any side-adjacent cards with zeroes in a row;  there wouldn't be a group of three consecutive cards containing numbers one. 

Today Vanya brought n cards with zeroes and m cards with numbers one. The number of cards was so much that the friends do not know how to put all those cards in the described way. Help them find the required arrangement of the cards or else tell the guys that it is impossible to arrange cards in such a way.


-----Input-----

The first line contains two integers: n (1 ≤ n ≤ 10^6) — the number of cards containing number 0; m (1 ≤ m ≤ 10^6) — the number of cards containing number 1.


-----Output-----

In a single line print the required sequence of zeroes and ones without any spaces. If such sequence is impossible to obtain, print -1.


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

Output
101

Input
4 8

Output
110110110101

Input
4 10

Output
11011011011011

Input
1 5

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a integer $n$ ($n > 0$). Find any integer $s$ which satisfies these conditions, or report that there are no such numbers:

In the decimal representation of $s$:   $s > 0$,  $s$ consists of $n$ digits,  no digit in $s$ equals $0$,  $s$ is not divisible by any of it's digits. 


-----Input-----

The input consists of multiple test cases. The first line of the input contains a single integer $t$ ($1 \leq t \leq 400$), the number of test cases. The next $t$ lines each describe a test case.

Each test case contains one positive integer $n$ ($1 \leq n \leq 10^5$).

It is guaranteed that the sum of $n$ for all test cases does not exceed $10^5$.


-----Output-----

For each test case, print an integer $s$ which satisfies the conditions described above, or "-1" (without quotes), if no such number exists. If there are multiple possible solutions for $s$, print any solution.


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

Output
-1
57
239
6789



-----Note-----

In the first test case, there are no possible solutions for $s$ consisting of one digit, because any such solution is divisible by itself.

For the second test case, the possible solutions are: $23$, $27$, $29$, $34$, $37$, $38$, $43$, $46$, $47$, $49$, $53$, $54$, $56$, $57$, $58$, $59$, $67$, $68$, $69$, $73$, $74$, $76$, $78$, $79$, $83$, $86$, $87$, $89$, $94$, $97$, and $98$.

For the third test case, one possible solution is $239$ because $239$ is not divisible by $2$, $3$ or $9$ and has three digits (none of which equals zero).

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

The game starts with `n` people standing in a circle. The presenter counts `m` people starting with the first one, and gives `1` coin to each of them. The rest of the players receive `2` coins each. After that, the last person who received `1` coin leaves the circle, giving everything he had to the next participant (who will also be considered "the first in the circle" in the next round). This process continues until only 1 person remains.

Determine the `number` of this person and how many `coins` he has at the end of the game.

The result should be a pair of values in the format: `[person, coins]`.

## Example:

```
n = 8, m = 3

People
1 2 3      1 2 ∙      1 2 ∙      ∙ 2 ∙       ∙  2 ∙       ∙ ∙  ∙       ∙ ∙  ∙
8   4  =>  8   4  =>  8   4  =>  8   4  =>   8    4  =>   8    4  =>   ∙    4  =>  7
7 6 5      7 6 5      7 ∙ 5      7 ∙ 5       7  ∙ ∙       7 ∙  ∙       7 ∙  ∙

Coins
0 0 0      1 1 ∙      3 3 ∙      ∙ 9 ∙       ∙ 10 ∙       ∙ ∙  ∙       ∙ ∙  ∙   
0   0  =>  2   3  =>  4   4  =>  5   6  =>   7    7  =>   8   20  =>   ∙   30  =>  51
0 0 0      2 2 2      7 ∙ 3      8 ∙ 5      16 ∙  ∙      17 ∙  ∙      18 ∙  ∙ 
```

## Notes:

* The presenter can do several full circles during one counting.
* In this case, the same person will receive `1` coin multiple times, i.e. no matter how many people are left in the circle, at least `m` coins will always be distributed among the participants during the round.
* If a person had already received `1` coin (possibly multiple times), he won't receive any additional `2` coins **at once(!)** during that round.
* People are counted starting with `1`.
* `m` can be **bigger** than `n` at start

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The commonly used bills in Japan are 10000-yen, 5000-yen and 1000-yen bills. Below, the word "bill" refers to only these.

According to Aohashi, he received an otoshidama (New Year money gift) envelope from his grandfather that contained N bills for a total of Y yen, but he may be lying. Determine whether such a situation is possible, and if it is, find a possible set of bills contained in the envelope. Assume that his grandfather is rich enough, and the envelope was large enough.

Constraints

* 1 ≤ N ≤ 2000
* 1000 ≤ Y ≤ 2 × 10^7
* N is an integer.
* Y is a multiple of 1000.

Input

Input is given from Standard Input in the following format:


N Y


Output

If the total value of N bills cannot be Y yen, print `-1 -1 -1`.

If the total value of N bills can be Y yen, let one such set of bills be "x 10000-yen bills, y 5000-yen bills and z 1000-yen bills", and print x, y, z with spaces in between. If there are multiple possibilities, any of them may be printed.

Examples

Input

9 45000


Output

4 0 5


Input

20 196000


Output

-1 -1 -1


Input

1000 1234000


Output

14 27 959


Input

2000 20000000


Output

2000 0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the cold and remote areas of northern Sweden, a young boy named Anton lives. Being born to a family of pistvakts (an occupation that involves drinking moonshine called “bäverhojt”, hunting bears and occasionally handling safety in the mountains), he has been handed the responsibility of mounting temperature sensors in the Scandinavian Mountains. Anton has to place three identical sensors along the mountain range, which can be modeled as a one-dimensional number line.

A lot of snow fell during the winter, and the sensors need to be placed at points with an ascending order of snow levels, since they work best arranged that way. This means that at the point of the leftmost sensor, the snow level must be strictly less than that of the other sensors, and at the point of the rightmost sensor, the snow level must instead be the strictly higher than that of the other sensors. Anton may also only place sensors at integer points. His house is located at point $0$, and no sensor may be placed to the left of the house.

Even with this limitation, there can be a huge number of ways in which he can place the sensors. Anton has saved the log of where snow has fallen during the winter, given as a number of ranges $[a, b]$, indicating that 1 meter of snow fell between and including points $a$ and $b$. If snow fell $k$ times over a certain point, the snow level in that point is $k$. Can you help him calculate the number of ways he may place the sensors?

-----Input-----
The first line of input contains a number $0 \le n \le 10^5$, the number of entries Anton has in his snow log. Then follow $n$ lines, each containing the two numbers $0 \le a \le b \le 10^{18}$, denoting an interval in which snow fell.

-----Output-----
Output consists of a single integer – the number of ways in which Anton can place the sensors. This number may be large, so output the remainder modulo $1000000009$. If there is no way Anton can place the sensors, you should instead output the string “shovel time!”, since Anton then must take his snowmobile and manually construct three points with the sought property.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a very busy person, with a lot of important meetings. Today, you have a meeting for which it is insanely important to arrive at the agreed time. 

Luckily you live in Zürich, which features a large network of extremely punctual trams. Each tram line travels from one place to another at regular intervals, always taking the same time from departure to arrival. It is very easy to change trams, and we assume that it takes no time to change to another tram if both are at a stop at the same time. This means that if a tram arrives at its destination at exactly time $t$ and another tram departs from the same place at time $t$ (or later), you will have enough time to change tram.

You are currently working in your hotel room before the meeting. Since you are a very busy person, you would like to leave your hotel at the latest possible time possible while still ariving to the meeting on time. When do you need to leave for your meeting?

-----Input-----
The input consists of:
 - one line with three integers $n$, $m$ and $s$ ($2 \le n \leq 100000$, $1 \le m \leq 200000$, $1 \le s \leq 10^9$), the number of tram stops, the number of tram lines, and the time at which the meeting starts in seconds relative to now.
 - $m$ lines, each with five integers $u, v, t_0, p, d$ ($0 \le u \not= v < n$, $0 \le t_0 \le 10^9$, $1 \le p, d \le 10^9$). The $i$’th line describes the $i$’th tram line, which departs from tram stop $u$, arrives at tram stop $v$, starts its first departure $t_0$ seconds from now, departs every $p$ seconds from the first departure, and takes $d$ seconds from departure to arrival.

The stops are numbered between $0$ and $n - 1$. Your hotel is located at stop $0$, and the meeting is at stop $n - 1$.

-----Output-----
Output the latest time at which you can leave the hotel while arriving to your meeting on time, in seconds from now. If you can not make it to your meeting on time, output impossible instead.

-----Examples-----
Sample Input:
2 1 10
0 1 1 2 6
Sample Output:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pavel loves grid mazes. A grid maze is an n × m rectangle maze where each cell is either empty, or is a wall. You can go from one cell to another only if both cells are empty and have a common side.

Pavel drew a grid maze with all empty cells forming a connected area. That is, you can go from any empty cell to any other one. Pavel doesn't like it when his maze has too little walls. He wants to turn exactly k empty cells into walls so that all the remaining cells still formed a connected area. Help him.


-----Input-----

The first line contains three integers n, m, k (1 ≤ n, m ≤ 500, 0 ≤ k < s), where n and m are the maze's height and width, correspondingly, k is the number of walls Pavel wants to add and letter s represents the number of empty cells in the original maze.

Each of the next n lines contains m characters. They describe the original maze. If a character on a line equals ".", then the corresponding cell is empty and if the character equals "#", then the cell is a wall.


-----Output-----

Print n lines containing m characters each: the new maze that fits Pavel's requirements. Mark the empty cells that you transformed into walls as "X", the other cells must be left without changes (that is, "." and "#").

It is guaranteed that a solution exists. If there are multiple solutions you can output any of them.


-----Examples-----
Input
3 4 2
#..#
..#.
#...

Output
#.X#
X.#.
#...

Input
5 4 5
#...
#.#.
.#..
...#
.#.#

Output
#XXX
#X#.
X#..
...#
.#.#

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A ball will bounce along a number line, making N + 1 bounces. It will make the first bounce at coordinate D_1 = 0, and the i-th bounce (2 \leq i \leq N+1) at coordinate D_i = D_{i-1} + L_{i-1}.
How many times will the ball make a bounce where the coordinate is at most X?

-----Constraints-----
 - 1 \leq N \leq 100
 - 1 \leq L_i \leq 100
 - 1 \leq X \leq 10000
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N X
L_1 L_2 ... L_{N-1} L_N

-----Output-----
Print the number of times the ball will make a bounce where the coordinate is at most X.

-----Sample Input-----
3 6
3 4 5

-----Sample Output-----
2

The ball will make a bounce at the coordinates 0, 3, 7 and 12, among which two are less than or equal to 6.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Berland scientists face a very important task - given the parts of short DNA fragments, restore the dinosaur DNA! The genome of a berland dinosaur has noting in common with the genome that we've used to: it can have 26 distinct nucleotide types, a nucleotide of each type can occur at most once. If we assign distinct English letters to all nucleotides, then the genome of a Berland dinosaur will represent a non-empty string consisting of small English letters, such that each letter occurs in it at most once.

Scientists have *n* genome fragments that are represented as substrings (non-empty sequences of consecutive nucleotides) of the sought genome.

You face the following problem: help scientists restore the dinosaur genome. It is guaranteed that the input is not contradictory and at least one suitable line always exists. When the scientists found out that you are a strong programmer, they asked you in addition to choose the one with the minimum length. If there are multiple such strings, choose any string.

Input Specification:
The first line of the input contains a positive integer *n* (1<=≤<=*n*<=≤<=100) — the number of genome fragments.

Each of the next lines contains one descriptions of a fragment. Each fragment is a non-empty string consisting of distinct small letters of the English alphabet. It is not guaranteed that the given fragments are distinct. Fragments could arbitrarily overlap and one fragment could be a substring of another one.

It is guaranteed that there is such string of distinct letters that contains all the given fragments as substrings.

Output Specification:
In the single line of the output print the genome of the minimum length that contains all the given parts. All the nucleotides in the genome must be distinct. If there are multiple suitable strings, print the string of the minimum length. If there also are multiple suitable strings, you can print any of them.

Demo Input:
['3\nbcd\nab\ncdef\n', '4\nx\ny\nz\nw\n']

Demo Output:
['abcdef\n', 'xyzw\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everybody loves magic, especially magicians who compete for glory on the Byteland Magic Tournament. Magician Cyael is one such magician.
Cyael has been having some issues with her last performances and today she’ll have to perform for an audience of some judges, who will change her tournament ranking, possibly increasing it. As she is a great magician she managed to gather a description of the fixed judges’ disposition on the room (which is represented as an N × N square matrix), such that she knows in advance the fixed points each judge will provide. She also knows that the room is divided into several parallel corridors, such that we will denote the j-th cell on corridor i, as [i][j]. Note that some judges can award Cyael, zero points or negative points, as they are never pleased with her performance.
There is just one judge at each cell of the matrix, except the cells [1][1] and [N][N].
To complete her evaluation, she must start on the top leftmost corner of the room (cell [1][1]), and finish on the bottom right corner (cell [N][N]), moving either to the cell directly in front of her on the same corridor (that is, moving from cell [r][c] to cell [r][c+1], where c+1 ≤ N) or to the cell in the next corridor directly in front of where she is (that is, moving from cell [r][c] to cell [r+1][c], where r+1 ≤ N). She will keep doing this until she reaches the end point of the room, i.e. last cell [N][N] on the last corridor. Cyael will be judged at all visited cells with a judge.

Cyael wants to maximize her average score at end of her performance. More specifically, if she passes K judges, each being on cell [i1][j1], cell [i2][j2], ..., cell [iK][jK] respectively, then she wants to maximize (S[i1][j1] + S[i2][j2] + ... + S[iK][jK]) / K, where S[i][j] denotes the points that the judge will give her on the cell [i][j].
Help her determine the best path she has to follow in order to maximize her average points.

Input
The first line contains a single integer T denoting the number of test cases. The description for T test cases follows. For each test case, the first line contains a single integer N. Each of the next N lines contains N space-separated integers.
The j-th integer S[i][j] in i-th line denotes the points awarded by the judge at cell [i][j].
Note that the cells [1][1] and [N][N] have no judges, so S[1][1] and S[N][N] will be 0.

Output
For each test case, if the maximum possible average points Cyael can obtain is negative, output a single line containing "Bad Judges" (quotes for clarity). Otherwise, output the maximum possible average points. The answer will be considered correct if it has an absolute error no more than  10^-6.

Constraints
1 ≤ T ≤ 202 ≤ N ≤ 100-2500 ≤ S[i][j] ≤ 2500S[1][1] = S[N][N] = 0
Your code will be judged against several input files. 

Example

Input:
2
2
0 -4
8 0
2
0 -45
-3  0


Output:
8.000000
Bad Judges

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Magnus decided to play a classic chess game. Though what he saw in his locker shocked him! His favourite chessboard got broken into 4 pieces, each of size n by n, n is always odd. And what's even worse, some squares were of wrong color. j-th square of the i-th row of k-th piece of the board has color a_{k}, i, j; 1 being black and 0 being white. 

Now Magnus wants to change color of some squares in such a way that he recolors minimum number of squares and obtained pieces form a valid chessboard. Every square has its color different to each of the neightbouring by side squares in a valid board. Its size should be 2n by 2n. You are allowed to move pieces but not allowed to rotate or flip them.


-----Input-----

The first line contains odd integer n (1 ≤ n ≤ 100) — the size of all pieces of the board. 

Then 4 segments follow, each describes one piece of the board. Each consists of n lines of n characters; j-th one of i-th line is equal to 1 if the square is black initially and 0 otherwise. Segments are separated by an empty line.


-----Output-----

Print one number — minimum number of squares Magnus should recolor to be able to obtain a valid chessboard.


-----Examples-----
Input
1
0

0

1

0

Output
1

Input
3
101
010
101

101
000
101

010
101
011

010
101
010

Output
2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity.

Your favorite store sells lemonade in bottles of *n* different volumes at different costs. A single bottle of type *i* has volume 2*i*<=-<=1 liters and costs *c**i* roubles. The number of bottles of each type in the store can be considered infinite.

You want to buy at least *L* liters of lemonade. How many roubles do you have to spend?

Input Specification:
The first line contains two integers *n* and *L* (1<=≤<=*n*<=≤<=30; 1<=≤<=*L*<=≤<=109) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively.

The second line contains *n* integers *c*1,<=*c*2,<=...,<=*c**n* (1<=≤<=*c**i*<=≤<=109) — the costs of bottles of different types.

Output Specification:
Output a single integer — the smallest number of roubles you have to pay in order to buy at least *L* liters of lemonade.

Demo Input:
['4 12\n20 30 70 90\n', '4 3\n10000 1000 100 10\n', '4 3\n10 100 1000 10000\n', '5 787787787\n123456789 234567890 345678901 456789012 987654321\n']

Demo Output:
['150\n', '10\n', '30\n', '44981600785557577\n']

Note:
In the first example you should buy one 8-liter bottle for 90 roubles and two 2-liter bottles for 30 roubles each. In total you'll get 12 liters of lemonade for just 150 roubles.

In the second example, even though you need only 3 liters, it's cheaper to buy a single 8-liter bottle for 10 roubles.

In the third example it's best to buy three 1-liter bottles for 10 roubles each, getting three liters for 30 roubles.

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