vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Mirko found a collection of $N$ toy tanks dating back to the Second World War on his grandfather’s attic. He promptly called his friend Slavko to play with him. They made a battlefield – a wooden board consisting of squares in $N$ rows and $N$ columns.

Each tank can be moved to one of the four neighbouring squares in a single move. A tank can shoot at any square in the same row and column. The tank is said to be guarding the row and column it is in.

Additionally, no two tanks can be in the same square at any time.

After many hours of play and two previous attempts, Mirko’s mom yelled at them to come down for lunch again, and they decided to rearrange the tanks so that each tank guards a different row and column (meaning also that each row and column contains only one tank).

However, they want to do this using the minimum number of moves.

Write a program that finds the minimum number of moves required to rearrange the tanks so that each row and each column contains a single tank, and one such shortest sequence of moves.

-----Input-----
The first line of input contains the integer $N$ ($3 \le N \le 500$).

Each of the following $N$ lines contains two integers $R$ and $C$ ($1 \le R, S \le N$), the row and column of a single tank at the moment of mom’s call. No two tanks are on the same square.

Rows and columns are marked $1$ through $N$, top-down and left-to-right.

-----Output-----
Output the minimum number of moves (call this number $K$) on the first line.

Each of the next $K$ lines should contain the tank being moved and the direction it is moved in, separated by a single space.

Tanks are numbered $1$ through $N$, in the order in which they are given in the input.

The direction can be one of four uppercase letters: ‘L’ for left, ‘R’ for right, ‘U’ for up and ‘D’ for down.

If there are multiple optimal solutions, any one will be accepted.

-----Examples-----
Sample Input 1:
5
1 1
1 2
1 3
1 4
1 5
Sample Output 1:
10
1 D
2 D
3 D
4 D
1 D
2 D
3 D
1 D
2 D
1 D

Sample Input 2:
5
2 3
3 2
3 3
3 4
4 3
Sample Output 2:
8
1 R
1 R
2 U
2 U
4 D
4 D
5 L
5 L

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a system of pipes. It consists of two rows, each row consists of $n$ pipes. The top left pipe has the coordinates $(1, 1)$ and the bottom right — $(2, n)$.

There are six types of pipes: two types of straight pipes and four types of curved pipes. Here are the examples of all six types:

 [Image] Types of pipes 

You can turn each of the given pipes $90$ degrees clockwise or counterclockwise arbitrary (possibly, zero) number of times (so the types $1$ and $2$ can become each other and types $3, 4, 5, 6$ can become each other).

You want to turn some pipes in a way that the water flow can start at $(1, 0)$ (to the left of the top left pipe), move to the pipe at $(1, 1)$, flow somehow by connected pipes to the pipe at $(2, n)$ and flow right to $(2, n + 1)$.

Pipes are connected if they are adjacent in the system and their ends are connected. Here are examples of connected pipes:

 [Image] Examples of connected pipes 

Let's describe the problem using some example:

 [Image] The first example input 

And its solution is below:  [Image] The first example answer 

As you can see, the water flow is the poorly drawn blue line. To obtain the answer, we need to turn the pipe at $(1, 2)$ $90$ degrees clockwise, the pipe at $(2, 3)$ $90$ degrees, the pipe at $(1, 6)$ $90$ degrees, the pipe at $(1, 7)$ $180$ degrees and the pipe at $(2, 7)$ $180$ degrees. Then the flow of water can reach $(2, n + 1)$ from $(1, 0)$.

You have to answer $q$ independent queries.


-----Input-----

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

Each query consists of exactly three lines. The first line of the query contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of pipes in each row. The next two lines contain a description of the first and the second rows correspondingly. Each row description consists of $n$ digits from $1$ to $6$ without any whitespaces between them, each digit corresponds to the type of pipe in the corresponding cell. See the problem statement to understand which digits correspond to which types of pipes.

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$.


-----Output-----

For the $i$-th query print the answer for it — "YES" (without quotes) if it is possible to turn some pipes in a way that the water flow can reach $(2, n + 1)$ from $(1, 0)$, and "NO" otherwise.


-----Example-----
Input
6
7
2323216
1615124
1
3
4
2
13
24
2
12
34
3
536
345
2
46
54

Output
YES
YES
YES
NO
YES
NO



-----Note-----

The first query from the example is described in the problem statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Gridnavia, three languages are spoken: Arwegian, Banish, and Cwedish. Gridnavia consists of an $n \times m$ grid, where at least one language is spoken in each cell. It is known that each of the three languages is spoken in a non-empty connected subset of grid cells. Connected means that it is possible to get between any pair of cells by moving through adjacent cells, where two cells are said to be adjacent if they share a side. 

You have made a survey to find where in Gridnavia each language is spoken. The following question was sent to every cell in the region: “Please indicate if one or several of the languages is spoken in your cell”. But due to a misprint, there were no choices after the question, so everyone just wrote “one” or “several”. So the only thing you know is for each cell whether exactly one, or more than one language is spoken in that cell.

To make the best out of the situation, you should find any division of the three languages that corresponds to the information.Input

The first line of input contains two integers $n$ and $m$ ($1 \leq n,m \leq 200$).

The following $n$ lines each contain a string of length $m$, consisting of the characters 1 and 2. The $j$th character on the $i$th line is 1 if exactly one language is spoken in that cell, and 2 if at least two languages are spoken.Output

If the languages can be divided according to the information, then output three copies of the grid. The first copy should consist of characters “A” and “.”, where the “A” indicates that Arwegian is spoken in that cell, and “.” indicates that it isn’t spoken. The following two grids should consist of characters “B” and “.”, and “C” and “.”, respectively, with the corresponding information about Banish and Cwedish.

Remember that the three regions have to be connected and non-empty, and every cell must be part of some region. For readability, it is recommended to put empty lines in between the three grids, but it is not necessary to do so. If there are multiple solutions any one will be accepted.

Otherwise, if there is no way to divide the languages, output “impossible”.

-----Examples-----
Sample Input:
3 4
2211
1112
1112
Sample Output:
AAAA
...A
....

BB..
BBBB
...B

....
...C
CCCC

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A positive integer a is given. Baron Munchausen claims that he knows such a positive integer n that if one multiplies n by a, the sum of its digits decreases a times. In other words, S(an) = S(n)/a, where S(x) denotes the sum of digits of the number x. 

Find out if what Baron told can be true.

Input

The only line contains a single integer a (2 ≤ a ≤ 10^3).

Output

If there is no such number n, print -1.

Otherwise print any appropriate positive integer n. Your number must not consist of more than 5⋅10^5 digits. We can show that under given constraints either there is no answer, or there is an answer no longer than 5⋅10^5 digits.

Examples

Input


2


Output


6


Input


3


Output


6669


Input


10


Output


-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima is a beginner programmer. During his working process, he regularly has to repeat the following operation again and again: to remove every second element from the array. One day he has been bored with easy solutions of this problem, and he has come up with the following extravagant algorithm.

Let's consider that initially array contains n numbers from 1 to n and the number i is located in the cell with the index 2i - 1 (Indices are numbered starting from one) and other cells of the array are empty. Each step Dima selects a non-empty array cell with the maximum index and moves the number written in it to the nearest empty cell to the left of the selected one. The process continues until all n numbers will appear in the first n cells of the array. For example if n = 4, the array is changing as follows: [Image] 

You have to write a program that allows you to determine what number will be in the cell with index x (1 ≤ x ≤ n) after Dima's algorithm finishes.


-----Input-----

The first line contains two integers n and q (1 ≤ n ≤ 10^18, 1 ≤ q ≤ 200 000), the number of elements in the array and the number of queries for which it is needed to find the answer.

Next q lines contain integers x_{i} (1 ≤ x_{i} ≤ n), the indices of cells for which it is necessary to output their content after Dima's algorithm finishes.


-----Output-----

For each of q queries output one integer number, the value that will appear in the corresponding array cell after Dima's algorithm finishes.


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

Output
3
2
4

Input
13 4
10
5
4
8

Output
13
3
8
9



-----Note-----

The first example is shown in the picture.

In the second example the final array is [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a set of $n$ intervals, find the size of its largest possible subset of intervals such that no three intervals in the subset share a common point.

Input Format

The first line contains an integer, $\boldsymbol{\mathrm{~S~}}$, denoting the number of interval sets you must find answers for. The $s\cdot(n+1)$ subsequent lines describe each of the $\boldsymbol{\mathrm{~S~}}$ interval sets as follows:

The first line contains an integer, $n$, denoting the number of intervals in the list. 
Each line $\boldsymbol{i}$ of the $n$ subsequent lines contains two space-separated integers describing the respective starting ($a_i$) and ending ($b_i$) boundaries of an interval.

Constraints

$1\leq s\leq100$
$2\leq n\leq1000$  
$1\leq a_i\leq b_i\leq10^9$

Output Format

For each of the $\boldsymbol{\mathrm{~S~}}$ interval sets, print an integer denoting the size of the largest possible subset of intervals in the given set such that no three points in the subset overlap.

Sample Input
4
3
1 2
2 3
2 4
3
1 5
1 5
1 5
4
1 10
1 3
4 6
7 10
4
1 10
1 3
3 6
7 10

Sample Output
2
2
4
3

Explanation

For set $\boldsymbol{s_{0}}$, all three intervals fall on point $2$ so we can only choose any $2$ of the intervals. Thus, we print $2$ on a new line.

For set $\boldsymbol{S_{1}}$, all three intervals span the range from $\mbox{1}$ to $5$ so we can only choose any $2$ of them. Thus, we print $2$ on a new line.

For set $s_2$, we can choose all $\begin{array}{c}4\end{array}$ intervals without having more than two of them overlap at any given point. Thus, we print $\begin{array}{c}4\end{array}$ on a new line.

For set $s_3$, the intervals $[1,10]$, $[1,3]$, and $[3,6]$ all overlap at point $3$, so we must only choose $2$ of these intervals to combine with the last interval, $[7,10]$, for a total of $3$ qualifying intervals. Thus, we print $3$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
UpCoder is looking to assign their best employees to a team tasked with designing their new and improved website, and they’re looking to you to help them form the team. There are $n$ potential candidates. The CEO is employee number $0$, and the candidates are all assigned employee numbers ranging from $1$ through $n$. Each candidate is recommended by an employee with a smaller employee number. Each candidate can be described by three numbers (in addition to their employee number): their negotiated salary, their expected productivity, and the number of the employee who recommended them.

You would like to assign exactly $k$ candidates out of the $n$ total candidates to the team. The total value that you can get from these candidates is the sum of their productivities divided by the sum of their salaries. Note that you may only assign a candidate to the team if their recommender is also part of the team, or is the CEO. So, at least one candidate that you assign needs to have the CEO as a reference. The CEO handles the business aspect of the company, so s/he will not be counted as part of the $k$ candidates chosen for the team.

Find the maximum total value your team can provide given these constraints.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of the input will consist of two space separated integers $k$ and $n$ ($1 \le k \le n \le 2500$), where $k$ is the size of the team you must form, and $n$ is the total number of employee candidates. Each of the following $n$ lines will hold three space-separated integers describing an employee. Employee $1$ will be described first, then employee $2$, and so on. The three integers are $s$, $p$ and $r$, where $s$ ($1 \le s \le 10000$) is the employee’s salary, $p$ ($1 \le p \le 10000$) is the employee’s productivity, and $r$ ($0 \le r<i$) is the employee number of the employee who recommended this candidate (where $i$ is the employee number of this candidate).

-----Output-----
Output a single real number, which represents the maximum total value you can achieve forming a team of $k$ employees, subject to the constraints of the problem. Output this number to exactly three decimal places, rounded (standard $5 \uparrow / 4 \downarrow $ rounding).

-----Examples-----
Sample Input:
1 2
1000 1 0
1 1000 1
Sample Output:
0.001

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Case of Fake Numbers

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Andrewid the Android is a galaxy-famous detective. He is now investigating a case of frauds who make fake copies of the famous Stolp's gears, puzzles that are as famous as the Rubik's cube once was.

Its most important components are a button and a line of *n* similar gears. Each gear has *n* teeth containing all numbers from 0 to *n*<=-<=1 in the counter-clockwise order. When you push a button, the first gear rotates clockwise, then the second gear rotates counter-clockwise, the the third gear rotates clockwise an so on.

Besides, each gear has exactly one active tooth. When a gear turns, a new active tooth is the one following after the current active tooth according to the direction of the rotation. For example, if *n*<==<=5, and the active tooth is the one containing number 0, then clockwise rotation makes the tooth with number 1 active, or the counter-clockwise rotating makes the tooth number 4 active.

Andrewid remembers that the real puzzle has the following property: you can push the button multiple times in such a way that in the end the numbers on the active teeth of the gears from first to last form sequence 0,<=1,<=2,<=...,<=*n*<=-<=1. Write a program that determines whether the given puzzle is real or fake.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=1000) — the number of gears.

The second line contains *n* digits *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=*n*<=-<=1) — the sequence of active teeth: the active tooth of the *i*-th gear contains number *a**i*.

Output Specification:
In a single line print "Yes" (without the quotes), if the given Stolp's gears puzzle is real, and "No" (without the quotes) otherwise.

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

Demo Output:
['Yes\n', 'Yes\n', 'No\n']

Note:
In the first sample test when you push the button for the first time, the sequence of active teeth will be 2 2 1, when you push it for the second time, you get 0 1 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two arrays $a$ and $b$, both of length $n$. All elements of both arrays are from $0$ to $n-1$.

You can reorder elements of the array $b$ (if you want, you may leave the order of elements as it is). After that, let array $c$ be the array of length $n$, the $i$-th element of this array is $c_i = (a_i + b_i) \% n$, where $x \% y$ is $x$ modulo $y$.

Your task is to reorder elements of the array $b$ to obtain the lexicographically minimum possible array $c$.

Array $x$ of length $n$ is lexicographically less than array $y$ of length $n$, if there exists such $i$ ($1 \le i \le n$), that $x_i < y_i$, and for any $j$ ($1 \le j < i$) $x_j = y_j$.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$, $b$ and $c$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < n$), where $a_i$ is the $i$-th element of $a$.

The third line of the input contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i < n$), where $b_i$ is the $i$-th element of $b$.


-----Output-----

Print the lexicographically minimum possible array $c$. Recall that your task is to reorder elements of the array $b$ and obtain the lexicographically minimum possible array $c$, where the $i$-th element of $c$ is $c_i = (a_i + b_i) \% n$.


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

Output
1 0 0 2 

Input
7
2 5 1 5 3 4 3
2 4 3 5 6 5 1

Output
0 0 0 1 0 2 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is well-known that the elephants are afraid of mouses. The Little Elephant from the Zoo of Lviv is not an exception.

The Little Elephant is on a board A of n rows and m columns (0-based numeration). At the beginning he is in cell with coordinates (0; 0) and he wants to go to cell with coordinates (n-1; m-1). From cell (x; y) Little Elephant can go either to (x+1; y) or (x; y+1).

Each cell of the board contains either 1 or 0. If A[i][j] = 1, then there is a single mouse in cell (i; j). Mouse at cell (i; j) scared Little Elephants if and only if during the path there was at least one such cell (x; y) (which belongs to that path) and |i-x| + |j-y| <= 1.

Little Elephant wants to find some correct path from (0; 0) to (n-1; m-1) such that the number of mouses that have scared the Little Elephant is minimal possible. Print that number.

-----Input-----
First line contains single integer T - the number of test cases. Then T test cases follow. First line of each test case contain pair of integers n and m - the size of the board. Next n lines contain n strings, each of size m and consisted of digits 0 and 1.

-----Output-----
In T lines print T integer - the answers for the corresponding test.

-----Constraints-----
1 <= T <= 50
2 <= n, m <= 100

-----Example-----
Input:
2
3 9
001000001
111111010
100100100
7 9
010101110
110110111
010011111
100100000
000010100
011011000
000100101

Output:
9
10

-----Explanation-----
Example case 1: 
The optimized path is: (0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (0, 4) -> (0, 5) -> (0, 6) -> (0, 7) -> (0, 8) -> (1, 8) -> (2, 8). The mouses that scared the Little Elephant are at the following cells: (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 7), (0, 2), (0, 8).

Example case 2: 
The optimized path is: (0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3) -> (4, 3) -> (4, 4) -> (5, 4) -> (5, 5) -> (6, 5) -> (6, 6) -> (6, 7) -> (6, 8). The 10 mouses that scared the Little Elephant are at the following cells: (0, 1), (1, 0), (1, 1), (2, 1), (3, 3), (4, 4), (5, 4), (5, 5), (6, 6), (6, 8).

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Professor Vasechkin is studying evolution of worms. Recently he put forward hypotheses that all worms evolve by division. There are *n* forms of worms. Worms of these forms have lengths *a*1, *a*2, ..., *a**n*. To prove his theory, professor needs to find 3 different forms that the length of the first form is equal to sum of lengths of the other two forms. Help him to do this.

Input Specification:
The first line contains integer *n* (3<=≤<=*n*<=≤<=100) — amount of worm's forms. The second line contains *n* space-separated integers *a**i* (1<=≤<=*a**i*<=≤<=1000) — lengths of worms of each form.

Output Specification:
Output 3 distinct integers *i* *j* *k* (1<=≤<=*i*,<=*j*,<=*k*<=≤<=*n*) — such indexes of worm's forms that *a**i*<==<=*a**j*<=+<=*a**k*. If there is no such triple, output -1. If there are several solutions, output any of them. It possible that *a**j*<==<=*a**k*.

Demo Input:
['5\n1 2 3 5 7\n', '5\n1 8 1 5 1\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Function Descriptions=====
Transpose

We can generate the transposition of an array using the tool numpy.transpose.
It will not affect the original array, but it will create a new array.

import numpy

my_array = numpy.array([[1,2,3],
                        [4,5,6]])
print numpy.transpose(my_array)

#Output
[[1 4]
 [2 5]
 [3 6]]

Flatten

The tool flatten creates a copy of the input array flattened to one dimension.

import numpy

my_array = numpy.array([[1,2,3],
                        [4,5,6]])
print my_array.flatten()

#Output
[1 2 3 4 5 6]

=====Problem Statement=====
You are given a NXM integer array matrix with space separated elements (N = rows and M = columns).
Your task is to print the transpose and flatten results.

=====Input Format=====
The first line contains the space separated values of N and M.
The next N lines contains the space separated elements of M columns.

=====Output Format=====
First, print the transpose array and then print the flatten.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N sticks with negligible thickness.
The length of the i-th stick is A_i.
Snuke wants to select four different sticks from these sticks and form a rectangle (including a square), using the sticks as its sides.
Find the maximum possible area of the rectangle.

-----Constraints-----
 - 4 \leq N \leq 10^5
 - 1 \leq A_i \leq 10^9
 - A_i is an integer.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print the maximum possible area of the rectangle.
If no rectangle can be formed, print 0.

-----Sample Input-----
6
3 1 2 4 2 1

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

1 \times 2 rectangle can be formed.

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