vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Sets

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Little Vasya likes very much to play with sets consisting of positive integers. To make the game more interesting, Vasya chose *n* non-empty sets in such a way, that no two of them have common elements.

One day he wanted to show his friends just how interesting playing with numbers is. For that he wrote out all possible unions of two different sets on *n*·(*n*<=-<=1)<=/<=2 pieces of paper. Then he shuffled the pieces of paper. He had written out the numbers in the unions in an arbitrary order.

For example, if *n*<==<=4, and the actual sets have the following form {1,<=3}, {5}, {2,<=4}, {7}, then the number of set pairs equals to six. The six pieces of paper can contain the following numbers: 
 -  2,<=7,<=4. -  1,<=7,<=3; -  5,<=4,<=2; -  1,<=3,<=5; -  3,<=1,<=2,<=4; -  5,<=7. 
Then Vasya showed the pieces of paper to his friends, but kept the *n* sets secret from them. His friends managed to calculate which sets Vasya had thought of in the first place. And how about you, can you restore the sets by the given pieces of paper?

Input Specification:
The first input file line contains a number *n* (2<=≤<=*n*<=≤<=200), *n* is the number of sets at Vasya's disposal. Then follow sets of numbers from the pieces of paper written on *n*·(*n*<=-<=1)<=/<=2 lines. Each set starts with the number *k**i* (2<=≤<=*k**i*<=≤<=200), which is the number of numbers written of the *i*-th piece of paper, and then follow *k**i* numbers *a**ij* (1<=≤<=*a**ij*<=≤<=200). All the numbers on the lines are separated by exactly one space. It is guaranteed that the input data is constructed according to the above given rules from *n* non-intersecting sets.

Output Specification:
Print on *n* lines Vasya's sets' description. The first number on the line shows how many numbers the current set has. Then the set should be recorded by listing its elements. Separate the numbers by spaces. Each number and each set should be printed exactly once. Print the sets and the numbers in the sets in any order. If there are several answers to that problem, print any of them.

It is guaranteed that there is a solution.

Demo Input:
['4\n3 2 7 4\n3 1 7 3\n3 5 4 2\n3 1 3 5\n4 3 1 2 4\n2 5 7\n', '4\n5 6 7 8 9 100\n4 7 8 9 1\n4 7 8 9 2\n3 1 6 100\n3 2 6 100\n2 1 2\n', '3\n2 1 2\n2 1 3\n2 2 3\n']

Demo Output:
['1 7 \n2 2 4 \n2 1 3 \n1 5 \n', '3 7 8 9 \n2 6 100 \n1 1 \n1 2 \n', '1 1 \n1 2 \n1 3 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your job is to write function last_digits(n,d) which return the last `d` digits of an integer `n` as a list.
`n` will be from 0 to 10^10

Examples:

`last_digits(1,1)     --> [1]`

`last_digits(1234,2)   --> [3,4]`

`last_digits(637547,6) --> [6,3,7,5,4,7]`

Special cases:

If `d` > the number of digits, just return the number's digits as a list.

If `d` <= 0, then return an empty list.

This is the first kata I have made, so please report any issues.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sherlock Holmes and Dr. Watson played some game on a checkered board *n*<=×<=*n* in size. During the game they put numbers on the board's squares by some tricky rules we don't know. However, the game is now over and each square of the board contains exactly one number. To understand who has won, they need to count the number of winning squares. To determine if the particular square is winning you should do the following. Calculate the sum of all numbers on the squares that share this column (including the given square) and separately calculate the sum of all numbers on the squares that share this row (including the given square). A square is considered winning if the sum of the column numbers is strictly greater than the sum of the row numbers.

For instance, lets game was ended like is shown in the picture. Then the purple cell is winning, because the sum of its column numbers equals 8<=+<=3<=+<=6<=+<=7<==<=24, sum of its row numbers equals 9<=+<=5<=+<=3<=+<=2<==<=19, and 24<=&gt;<=19.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=30). Each of the following *n* lines contain *n* space-separated integers. The *j*-th number on the *i*-th line represents the number on the square that belongs to the *j*-th column and the *i*-th row on the board. All number on the board are integers from 1 to 100.

Output Specification:
Print the single number — the number of the winning squares.

Demo Input:
['1\n1\n', '2\n1 2\n3 4\n', '4\n5 7 8 4\n9 5 3 2\n1 6 6 4\n9 5 7 3\n']

Demo Output:
['0\n', '2\n', '6\n']

Note:
In the first example two upper squares are winning.

In the third example three left squares in the both middle rows are winning:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Many schoolchildren look for a job for the summer, and one day, when Gerald was still a schoolboy, he also decided to work in the summer. But as Gerald was quite an unusual schoolboy, he found quite unusual work. A certain Company agreed to pay him a certain sum of money if he draws them three identical circles on a plane. The circles must not interfere with each other (but they may touch each other). He can choose the centers of the circles only from the n options granted by the Company. He is free to choose the radius of the circles himself (all three radiuses must be equal), but please note that the larger the radius is, the more he gets paid. 

Help Gerald earn as much as possible.

Input

The first line contains a single integer n — the number of centers (3 ≤ n ≤ 3000). The following n lines each contain two integers xi, yi ( - 104 ≤ xi, yi ≤ 104) — the coordinates of potential circle centers, provided by the Company.

All given points are distinct.

Output

Print a single real number — maximum possible radius of circles. The answer will be accepted if its relative or absolute error doesn't exceed 10 - 6.

Examples

Input

3
0 1
1 0
1 1


Output

0.50000000000000000000


Input

7
2 -3
-2 -3
3 0
-3 -1
1 -2
2 -2
-1 0


Output

1.58113883008418980000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ of length $n$ consisting of zeros. You perform $n$ actions with this array: during the $i$-th action, the following sequence of operations appears:  Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one;  Let this segment be $[l; r]$. If $r-l+1$ is odd (not divisible by $2$) then assign (set) $a[\frac{l+r}{2}] := i$ (where $i$ is the number of the current action), otherwise (if $r-l+1$ is even) assign (set) $a[\frac{l+r-1}{2}] := i$. 

Consider the array $a$ of length $5$ (initially $a=[0, 0, 0, 0, 0]$). Then it changes as follows:  Firstly, we choose the segment $[1; 5]$ and assign $a[3] := 1$, so $a$ becomes $[0, 0, 1, 0, 0]$;  then we choose the segment $[1; 2]$ and assign $a[1] := 2$, so $a$ becomes $[2, 0, 1, 0, 0]$;  then we choose the segment $[4; 5]$ and assign $a[4] := 3$, so $a$ becomes $[2, 0, 1, 3, 0]$;  then we choose the segment $[2; 2]$ and assign $a[2] := 4$, so $a$ becomes $[2, 4, 1, 3, 0]$;  and at last we choose the segment $[5; 5]$ and assign $a[5] := 5$, so $a$ becomes $[2, 4, 1, 3, 5]$. 

Your task is to find the array $a$ of length $n$ after performing all $n$ actions. Note that the answer exists and unique.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer — the array $a$ of length $n$ after performing $n$ actions described in the problem statement. Note that the answer exists and unique.


-----Example-----
Input
6
1
2
3
4
5
6

Output
1 
1 2 
2 1 3 
3 1 2 4 
2 4 1 3 5 
3 4 1 5 2 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given four integers $n$, $c_0$, $c_1$ and $h$ and a binary string $s$ of length $n$.

A binary string is a string consisting of characters $0$ and $1$.

You can change any character of the string $s$ (the string should be still binary after the change). You should pay $h$ coins for each change.

After some changes (possibly zero) you want to buy the string. To buy the string you should buy all its characters. To buy the character $0$ you should pay $c_0$ coins, to buy the character $1$ you should pay $c_1$ coins.

Find the minimum number of coins needed to buy the string.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 10$) — the number of test cases. Next $2t$ lines contain descriptions of test cases.

The first line of the description of each test case contains four integers $n$, $c_{0}$, $c_{1}$, $h$ ($1 \leq n, c_{0}, c_{1}, h \leq 1000$).

The second line of the description of each test case contains the binary string $s$ of length $n$.


-----Output-----

For each test case print a single integer — the minimum number of coins needed to buy the string.


-----Examples-----

Input
6
3 1 1 1
100
5 10 100 1
01010
5 10 1 1
11111
5 1 10 1
11111
12 2 1 10
101110110101
2 100 1 10
00
Output
3
52
5
10
16
22


-----Note-----

In the first test case, you can buy all characters and pay $3$ coins, because both characters $0$ and $1$ costs $1$ coin.

In the second test case, you can firstly change $2$-nd and $4$-th symbols of the string from $1$ to $0$ and pay $2$ coins for that. Your string will be $00000$. After that, you can buy the string and pay $5 \cdot 10 = 50$ coins for that. The total number of coins paid will be $2 + 50 = 52$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya has become interested in wrestling. In wrestling wrestlers use techniques for which they are awarded points by judges. The wrestler who gets the most points wins.

When the numbers of points of both wrestlers are equal, the wrestler whose sequence of points is lexicographically greater, wins.

If the sequences of the awarded points coincide, the wrestler who performed the last technique wins. Your task is to determine which wrestler won.

Input Specification:
The first line contains number *n* — the number of techniques that the wrestlers have used (1<=≤<=*n*<=≤<=2·105). 

The following *n* lines contain integer numbers *a**i* (|*a**i*|<=≤<=109, *a**i*<=≠<=0). If *a**i* is positive, that means that the first wrestler performed the technique that was awarded with *a**i* points. And if *a**i* is negative, that means that the second wrestler performed the technique that was awarded with (<=-<=*a**i*) points.

The techniques are given in chronological order.

Output Specification:
If the first wrestler wins, print string "first", otherwise print "second"

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

Demo Output:
['second\n', 'first\n', 'second\n']

Note:
Sequence *x*  =  *x*<sub class="lower-index">1</sub>*x*<sub class="lower-index">2</sub>... *x*<sub class="lower-index">|*x*|</sub> is lexicographically larger than sequence *y*  =  *y*<sub class="lower-index">1</sub>*y*<sub class="lower-index">2</sub>... *y*<sub class="lower-index">|*y*|</sub>, if either |*x*|  &gt;  |*y*| and *x*<sub class="lower-index">1</sub>  =  *y*<sub class="lower-index">1</sub>,  *x*<sub class="lower-index">2</sub>  =  *y*<sub class="lower-index">2</sub>, ... ,  *x*<sub class="lower-index">|*y*|</sub>  =  *y*<sub class="lower-index">|*y*|</sub>, or there is such number *r* (*r*  &lt;  |*x*|, *r*  &lt;  |*y*|), that *x*<sub class="lower-index">1</sub>  =  *y*<sub class="lower-index">1</sub>,  *x*<sub class="lower-index">2</sub>  =  *y*<sub class="lower-index">2</sub>,  ... ,  *x*<sub class="lower-index">*r*</sub>  =  *y*<sub class="lower-index">*r*</sub> and *x*<sub class="lower-index">*r*  +  1</sub>  &gt;  *y*<sub class="lower-index">*r*  +  1</sub>.

We use notation |*a*| to denote length of sequence *a*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lot of junior developer can be stuck when they need to change the access permission to a file or a directory in an Unix-like operating systems.

To do that they can use the `chmod` command and with some magic trick they can change the permissionof a file or a directory. For more information about the `chmod` command you can take a look at the [wikipedia page](https://en.wikipedia.org/wiki/Chmod).

`chmod` provides two types of syntax that can be used for changing permissions. An absolute form using octal to denote which permissions bits are set e.g: 766.
Your goal in this kata is to define the octal you need to use in order to set yout permission correctly.

Here is the list of the permission you can set with the octal representation of this one.

- User
  - read (4)
  - write (2)
  - execute (1)
- Group
  - read (4)
  - write (2)
  - execute (1)
- Other
  - read (4)
  - write (2)
  - execute (1)
  
The method take a hash in argument this one can have a maximum of 3 keys (`owner`,`group`,`other`). Each key will have a 3 chars string to represent the permission, for example the string `rw-` say that the user want the permission `read`, `write` without the `execute`.
If a key is missing set the permission to `---`

**Note**: `chmod` allow you to set some special flags too (`setuid`, `setgid`, `sticky bit`) but to keep some simplicity for this kata we will ignore this one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you know, majority of students and teachers of Summer Informatics School live in Berland for the most part of the year. Since corruption there is quite widespread, the following story is not uncommon.

Elections are coming. You know the number of voters and the number of parties — $n$ and $m$ respectively. For each voter you know the party he is going to vote for. However, he can easily change his vote given a certain amount of money. In particular, if you give $i$-th voter $c_i$ bytecoins you can ask him to vote for any other party you choose.

The United Party of Berland has decided to perform a statistical study — you need to calculate the minimum number of bytecoins the Party needs to spend to ensure its victory. In order for a party to win the elections, it needs to receive strictly more votes than any other party.


-----Input-----

The first line of input contains two integers $n$ and $m$ ($1 \le n, m \le 3000$) — the number of voters and the number of parties respectively.

Each of the following $n$ lines contains two integers $p_i$ and $c_i$ ($1 \le p_i \le m$, $1 \le c_i \le 10^9$) — the index of this voter's preferred party and the number of bytecoins needed for him to reconsider his decision.

The United Party of Berland has the index $1$.


-----Output-----

Print a single number — the minimum number of bytecoins needed for The United Party of Berland to win the elections.


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

Output
0

Input
5 5
2 100
3 200
4 300
5 400
5 900

Output
500

Input
5 5
2 100
3 200
4 300
5 800
5 900

Output
600



-----Note-----

In the first sample, The United Party wins the elections even without buying extra votes.

In the second sample, The United Party can buy the votes of the first and the fourth voter. This way The Party gets two votes, while parties $3$, $4$ and $5$ get one vote and party number $2$ gets no votes.

In the third sample, The United Party can buy the votes of the first three voters and win, getting three votes against two votes of the fifth party.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fibonacci numbers are the sequence of integers: f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5, ..., fn = fn - 2 + fn - 1. So every next number is the sum of the previous two.

Bajtek has developed a nice way to compute Fibonacci numbers on a blackboard. First, he writes a 0. Then, below it, he writes a 1. Then he performs the following two operations:

  * operation "T": replace the top number with the sum of both numbers; 
  * operation "B": replace the bottom number with the sum of both numbers. 



If he performs n operations, starting with "T" and then choosing operations alternately (so that the sequence of operations looks like "TBTBTBTB..."), the last number written will be equal to fn + 1.

Unfortunately, Bajtek sometimes makes mistakes and repeats an operation two or more times in a row. For example, if Bajtek wanted to compute f7, then he would want to do n = 6 operations: "TBTBTB". If he instead performs the sequence of operations "TTTBBT", then he will have made 3 mistakes, and he will incorrectly compute that the seventh Fibonacci number is 10. The number of mistakes in the sequence of operations is the number of neighbouring equal operations («TT» or «BB»).

You are given the number n of operations that Bajtek has made in an attempt to compute fn + 1 and the number r that is the result of his computations (that is last written number). Find the minimum possible number of mistakes that Bajtek must have made and any possible sequence of n operations resulting in r with that number of mistakes.

Assume that Bajtek always correctly starts with operation "T".

Input

The first line contains the integers n and r (1 ≤ n, r ≤ 106).

Output

The first line of the output should contain one number — the minimum possible number of mistakes made by Bajtek. The second line should contain n characters, starting with "T", describing one possible sequence of operations with that number of mistakes. Each character must be either "T" or "B".

If the required sequence doesn't exist, output "IMPOSSIBLE" (without quotes).

Examples

Input

6 10


Output

2
TBBTTB


Input

4 5


Output

0
TBTB


Input

2 1


Output

IMPOSSIBLE

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Oleg the bank client lives in Bankopolia. There are *n* cities in Bankopolia and some pair of cities are connected directly by bi-directional roads. The cities are numbered from 1 to *n*. There are a total of *m* roads in Bankopolia, the *i*-th road connects cities *u**i* and *v**i*. It is guaranteed that from each city it is possible to travel to any other city using some of the roads.

Oleg wants to give a label to each city. Suppose the label of city *i* is equal to *x**i*. Then, it must hold that for all pairs of cities (*u*,<=*v*) the condition |*x**u*<=-<=*x**v*|<=≤<=1 holds if and only if there is a road connecting *u* and *v*.

Oleg wonders if such a labeling is possible. Find an example of such labeling if the task is possible and state that it is impossible otherwise.

Input Specification:
The first line of input contains two space-separated integers *n* and *m* (2<=≤<=*n*<=≤<=3·105, 1<=≤<=*m*<=≤<=3·105) — the number of cities and the number of roads.

Next, *m* lines follow. The *i*-th line contains two space-separated integers *u**i* and *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*, *u**i*<=≠<=*v**i*) — the cities connected by the *i*-th road. It is guaranteed that there is at most one road between each pair of cities and it is possible to travel from any city to any other city using some roads.

Output Specification:
If the required labeling is not possible, output a single line containing the string "NO" (without quotes).

Otherwise, output the string "YES" (without quotes) on the first line. On the next line, output *n* space-separated integers, *x*1,<=*x*2,<=...,<=*x**n*. The condition 1<=≤<=*x**i*<=≤<=109 must hold for all *i*, and for all pairs of cities (*u*,<=*v*) the condition |*x**u*<=-<=*x**v*|<=≤<=1 must hold if and only if there is a road connecting *u* and *v*.

Demo Input:
['4 4\n1 2\n1 3\n1 4\n3 4\n', '5 10\n1 2\n1 3\n1 4\n1 5\n2 3\n2 4\n2 5\n3 4\n3 5\n5 4\n', '4 3\n1 2\n1 3\n1 4\n']

Demo Output:
['YES\n2 3 1 1 \n', 'YES\n1 1 1 1 1 \n', 'NO\n']

Note:
For the first sample, *x*<sub class="lower-index">1</sub> = 2, *x*<sub class="lower-index">2</sub> = 3, *x*<sub class="lower-index">3</sub> = *x*<sub class="lower-index">4</sub> = 1 is a valid labeling. Indeed, (3, 4), (1, 2), (1, 3), (1, 4) are the only pairs of cities with difference of labels not greater than 1, and these are precisely the roads of Bankopolia.

For the second sample, all pairs of cities have difference of labels not greater than 1 and all pairs of cities have a road connecting them.

For the last sample, it is impossible to construct a labeling satisfying the given constraints.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko has just installed a brand new drawing program. The program supports $K$ different colours, denoted by integers from 1 to $K$. All drawing is performed on a canvas with dimensions $N\times N$. In the beginning, all cells are white (denoted by 1).

The upper left cell of the canvas has coordinates $(0, 0)$. The first coordinate, $x$, increases iterating over rows, and the second, $y$, increases iterating over columns.

Mirko’s favourite pastime is drawing rectangular checkerboard patterns using the command PAINT c x1 y1 x2 y2, where $c$ denotes the chosen colour, and $(x1, y1)$ and $(x2, y2)$ are coordinates of the upper left and lower right cells, respectively, of the rectangle being painted.

The upper left cell of the rectangle will be painted in the chosen colour, while the rest are determined by the checkerboard pattern. Cells that are not painted over by the chosen colour will retain their previous colour. For example, a white canvas painted over by a red checkerboard pattern will look like this:

Mirko has recently discovered two additional commands. He can save his painting at any time using the creatively named command SAVE, and load it again later using the command LOAD x, where $x$ is a positive integer representing the ordinal number of the save.

Unfortunately, the program has crashed and Mirko’s painting is lost forever. Luckily, Mirko has saved a log of all used commands. Can you help Mirko by reconstructing the lost painting?

-----Input-----
The first line of input contains three positive integers, $N$ ($1 \leq N \leq 1000$), $K$ ($2 \leq K \leq 100000$), and $M$ ($1 \leq M \leq 100000$, $M$ is the number of commands).

Each of the following $M$ lines contains one of the three described commands. The input will not contain any illegal commands.

-----Output-----
Output $N$ lines, each containing N integers representing the colours of cells in the corresponding row of the painting.

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

Sample Input 2:
3 3 4
PAINT 3 0 0 1 1
SAVE
PAINT 2 1 1 2 2
LOAD 1
Sample Output 2:
3 1 1
1 3 1
1 1 1

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