vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
See Russian Translation

The end semester exams are now approaching. Ritu is the Computer Science Teacher of  Coder Public School. He has been assigned the task of preparing good algorithmic problems for the students by the Dean of the school.

Ritu like every other teacher has his own favorite topics. Ritu likes matrices and maths. So, he tries to create a problem that contains a mixture of both the things. After thinking for weeks, he comes up with a really awesome problem to blow away the minds of his students. But, before giving this problem in the exam he wants to check whether it's tough for his students or not. So, he gives his problem to you to solve so that he could decide whether his problem is good enough or not. So here goes the problem:

Given an N*N matrix where each cell in the matrix contains number between 1 to 100. The students are required to report the total number of decreasing paths.

From a particular cell (x,y) you can only go to cells (x+1,y) , (x-1,y) , (x,y+1) , (x,y-1) but you can't go outside the matrix, and you can't go to cell with higher or equal number than the number in current cell.

Since the number of such paths could be huge he asks them to tell him modulo 10^9+7. A path of only one cell is counted as a path.

So try your hand on Ritu's problem and give him a feedback on his problem so that he could decide whether his problem was good enough or not.

Input:

The first line contains the integer N denoting the size of matrix.

This is followed by N lines where each line contains N space separated integers.

Output:

Print the total number of such paths Modulo 10^9+7.

Constraints:

1 ≤ N ≤1000

1 ≤ Numbers in matrix cells ≤100

SAMPLE INPUT
2
1 2
1 3

SAMPLE OUTPUT
8

Explanation

Length 1 Paths : (1) , (1) , (2) , (3)

Length 2 Paths : (2,1) , (3,1) , (3,2)

Length 3 Paths : (3,2,1)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected unweighted connected graph consisting of $n$ vertices and $m$ edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Your task is to find any spanning tree of this graph such that the degree of the first vertex (vertex with label $1$ on it) is equal to $D$ (or say that there are no such spanning trees). Recall that the degree of a vertex is the number of edges incident to it.


-----Input-----

The first line contains three integers $n$, $m$ and $D$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2}), 1 \le D < n$) — the number of vertices, the number of edges and required degree of the first vertex, respectively.

The following $m$ lines denote edges: edge $i$ is represented by a pair of integers $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$), which are the indices of vertices connected by the edge. There are no loops or multiple edges in the given graph, i. e. for each pair ($v_i, u_i$) there are no other pairs ($v_i, u_i$) or ($u_i, v_i$) in the list of edges, and for each pair $(v_i, u_i)$ the condition $v_i \ne u_i$ is satisfied.


-----Output-----

If there is no spanning tree satisfying the condition from the problem statement, print "NO" in the first line.

Otherwise print "YES" in the first line and then print $n-1$ lines describing the edges of a spanning tree such that the degree of the first vertex (vertex with label $1$ on it) is equal to $D$. Make sure that the edges of the printed spanning tree form some subset of the input edges (order doesn't matter and edge $(v, u)$ is considered the same as the edge $(u, v)$).

If there are multiple possible answers, print any of them.


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

Output
YES
2 1
2 3
3 4

Input
4 5 3
1 2
1 3
1 4
2 3
3 4

Output
YES
1 2
1 3
4 1

Input
4 4 3
1 2
1 4
2 3
3 4

Output
NO



-----Note-----

The picture corresponding to the first and second examples: [Image]

The picture corresponding to the third example: [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a ternary string (it is a string which consists only of characters '0', '1' and '2').

You can swap any two adjacent (consecutive) characters '0' and '1' (i.e. replace "01" with "10" or vice versa) or any two adjacent (consecutive) characters '1' and '2' (i.e. replace "12" with "21" or vice versa).

For example, for string "010210" we can perform the following moves:   "010210" $\rightarrow$ "100210";  "010210" $\rightarrow$ "001210";  "010210" $\rightarrow$ "010120";  "010210" $\rightarrow$ "010201". 

Note than you cannot swap "02" $\rightarrow$ "20" and vice versa. You cannot perform any other operations with the given string excluding described above.

You task is to obtain the minimum possible (lexicographically) string by using these swaps arbitrary number of times (possibly, zero).

String $a$ is lexicographically less than string $b$ (if strings $a$ and $b$ have the same length) if there exists some position $i$ ($1 \le i \le |a|$, where $|s|$ is the length of the string $s$) such that for every $j < i$ holds $a_j = b_j$, and $a_i < b_i$.


-----Input-----

The first line of the input contains the string $s$ consisting only of characters '0', '1' and '2', its length is between $1$ and $10^5$ (inclusive).


-----Output-----

Print a single string — the minimum possible (lexicographically) string you can obtain by using the swaps described above arbitrary number of times (possibly, zero).


-----Examples-----
Input
100210

Output
001120

Input
11222121

Output
11112222

Input
20

Output
20

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are three positive integers A, B and C written on a blackboard. E869120 performs the following operation K times:
 - Choose one integer written on the blackboard and let the chosen integer be n. Replace the chosen integer with 2n.
What is the largest possible sum of the integers written on the blackboard after K operations?

-----Constraints-----
 - A, B and C are integers between 1 and 50 (inclusive).
 - K is an integer between 1 and 10 (inclusive).

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

-----Output-----
Print the largest possible sum of the integers written on the blackboard after K operations by E869220.

-----Sample Input-----
5 3 11
1

-----Sample Output-----
30

In this sample, 5, 3, 11 are initially written on the blackboard, and E869120 can perform the operation once.

There are three choices:  
 - Double 5: The integers written on the board after the operation are 10, 3, 11.
 - Double 3: The integers written on the board after the operation are 5, 6, 11.
 - Double 11: The integers written on the board after the operation are 5, 3, 22.
If he chooses 3., the sum of the integers written on the board afterwards is 5 + 3 + 22 = 30, which is the largest among 1. through 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
To add insult to injury, the zombies have taken all but two drawings from Heidi! Please help her recover the Tree of Life from only these two drawings.

Input

The input format is the same as in the medium version, except that now the bound on n is 2 ≤ n ≤ 1000 and that k = 2.

Output

The same as in the medium version.

Example

Input

1
9 2
6
4 3
5 4
6 1
8 6
8 2
7 1
5
8 6
8 7
8 1
7 3
5 1


Output

YES
2 1
3 1
5 4
6 5
7 6
8 5
9 8
1 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.
Here \gcd(a,b,c) denotes the greatest common divisor of a, b, and c.

-----Constraints-----
 - 1 \leq K \leq 200
 - K is an integer.

-----Input-----
Input is given from Standard Input in the following format:
K

-----Output-----
Print the value of \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.

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

-----Sample Output-----
9

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)+\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2)=1+1+1+1+1+1+1+2=9
Thus, the answer is 9.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
PolandBall lives in a forest with his family. There are some trees in the forest. Trees are undirected acyclic graphs with *k* vertices and *k*<=-<=1 edges, where *k* is some integer. Note that one vertex is a valid tree.

There is exactly one relative living in each vertex of each tree, they have unique ids from 1 to *n*. For each Ball *i* we know the id of its most distant relative living on the same tree. If there are several such vertices, we only know the value of the one with smallest id among those.

How many trees are there in the forest?

Input Specification:
The first line contains single integer *n* (1<=≤<=*n*<=≤<=104) — the number of Balls living in the forest.

The second line contains a sequence *p*1,<=*p*2,<=...,<=*p**n* of length *n*, where (1<=≤<=*p**i*<=≤<=*n*) holds and *p**i* denotes the most distant from Ball *i* relative living on the same tree. If there are several most distant relatives living on the same tree, *p**i* is the id of one with the smallest id.

It's guaranteed that the sequence *p* corresponds to some valid forest.

Hacking: To hack someone, you should provide a correct forest as a test. The sequence *p* will be calculated according to the forest and given to the solution you try to hack as input. Use the following format:

In the first line, output the integer *n* (1<=≤<=*n*<=≤<=104) — the number of Balls and the integer *m* (0<=≤<=*m*<=&lt;<=*n*) — the total number of edges in the forest. Then *m* lines should follow. The *i*-th of them should contain two integers *a**i* and *b**i* and represent an edge between vertices in which relatives *a**i* and *b**i* live. For example, the first sample is written as follows:

Output Specification:
You should output the number of trees in the forest where PolandBall lives.

Demo Input:
['5\n2 1 5 3 3', '1\n1\n']

Demo Output:
['2', '1']

Note:
In the first sample testcase, possible forest is: 1-2 3-4-5. 

There are 2 trees overall.

In the second sample testcase, the only possible graph is one vertex and no edges. Therefore, there is only one tree.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
Consider an array of integers `a`. Let `min(a)` be its minimal element, and let `avg(a)` be its mean.

Define the center of the array `a` as array `b` such that:

```
- b is formed from a by erasing some of its elements.
- For each i, |b[i] - avg(a)| < min(a).
- b has the maximum number of elements among all the arrays
  satisfying the above requirements.
```

Given an array of integers, return its center.



# Input/Output


`[input]` integer array `a`

 Unsorted non-empty array of integers.

`2 ≤ a.length ≤ 50,`

`1 ≤ a[i] ≤ 350.`

`[output]` an integer array


# Example

For `a = [8, 3, 4, 5, 2, 8]`, the output should be `[4, 5]`.

Here `min(a) = 2, avg(a) = 5`.

For `a = [1, 3, 2, 1]`, the output should be `[1, 2, 1]`.

Here `min(a) = 1, avg(a) = 1.75`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An extraterrestrial visit!
Remember your childhood friend JAADU from outer space?? Well, he is back again to our mighty Planet Earth.

But do you expect us geeks to introduce a character like Rohit Mehra in this story?

A Hell No!! 

Instead, he encounters the creepy Scientists of Planet Earth all the way from S.H.I.E.L.D led by the great Scientist Dr. Jackal (Yee Haw).
Dr. Jackal and his team capture JAADU and decide to carry out tests on him to study his biological structure (It’s not every day you get to slice open a real alien). To achieve this, scientists will have to study his genes which are organized in an infinitely long sequence of DNA strands in the body. DNA strands in his body are found to be encodings of the proteins G & C. Now they want to identify the gene core which is basically the K^th character in the N^th DNA strand.

You being a programmer are asked to devise a method to identify the gene core starting from the entry gene strand.
Scientists have identified the pattern in which gene strands are organized:

D1 = "G"

D2 = "GGC"

D3 = "GGCGGCC"

. . .

DN = D(N-1) + "G" + switch(reverse(D(N-1))).

Where
switch operation converts any G’s in the sequence to C’s and vice versa
and
reverse operation reverses the sequence.

Eg:

Switch(GGC) = CCG

Reverse(GGC) = CGG

You are asked to figure out the K^th character of the sequence DN. If the K^th character doesn't exist in the sequence DN, output -1.

Input Format
The first line contains T, then number of test cases.

T lines follow, each contains a value of N and K.

Output Format
For each test case, print the K^th character of the sequence DN (or -1 if it doesn't exist) in a separate line.

Constraints
1 ≤ T ≤ 10^5
1 ≤ N ≤ 50
1 ≤ K ≤ 10^16

SAMPLE INPUT
4
1 1
2 1
2 3
2 5

SAMPLE OUTPUT
G
G
C
-1

Explanation

See example given above.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a directed graph G with N vertices and M edges. The vertices are numbered 1, 2, \ldots, N, and for each i (1 \leq i \leq M), the i-th directed edge goes from Vertex x_i to y_i. G does not contain directed cycles.

Find the length of the longest directed path in G. Here, the length of a directed path is the number of edges in it.

Constraints

* All values in input are integers.
* 2 \leq N \leq 10^5
* 1 \leq M \leq 10^5
* 1 \leq x_i, y_i \leq N
* All pairs (x_i, y_i) are distinct.
* G does not contain directed cycles.

Input

Input is given from Standard Input in the following format:


N M
x_1 y_1
x_2 y_2
:
x_M y_M


Output

Print the length of the longest directed path in G.

Examples

Input

4 5
1 2
1 3
3 2
2 4
3 4


Output

3


Input

6 3
2 3
4 5
5 6


Output

2


Input

5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3


Output

3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As usual Alice and bob are playing a game. Alice will always take the first turn, after which they will take alternate turns and player who won't be able to make a move in 
his/her turn will loose the game. In starting Alice will be given number 'n'. A player in his turn can decrease the number given to him by either 'a' or 'b'(a and b are 
explained in last), after that he will give the resulted number 'x' ('x' is the resulted number after decreasing) to other player. Then other player will similarly 
decrease the number given to him by 'a' or 'b'. So a player in his/her turn have to perform two operations, first calculate the value of 'a' and 'b' for the number and 
then decrease the number either by 'a' or 'b'. Both alice and bob hate negative numbers, they also don't like positive numbers having one digit only. So they have 
to keep the number of digits in number at least 2 means they can't make the number less than 10. The player who won't be able to make a move in his turn will loose 
the game. Given the starting  number 'n' , you have to tell the winner of game assuming both players play optimally.

a: For a given number 'x', 'a' is number of prime numbers i such that 1 ≤ i ≤ x and gcd(i,x)=i. For example if player is holding 12 currently then 'a' is 2 (The numbers
satisfying the criteria are 2 and 3)

b: For a given number 'x', number of numbers i such that 1 ≤ i ≤ x and gcd(i,x)=1. For exmaple if player is holding 12 currently then 'b' is 4 ( The numbers satisfying 
the criteria are 1,5,7,11).

Input: First line will contain 't', no of test cases. After that there will be 't' lines each containging an integer 'n'.

Output: For each test case you have to print the winner of the game, "Alice" or "Bob" (without quotes).

Constraints:
1 ≤ t ≤ 1000

10 ≤ n ≤ 1000000 (10^6)

SAMPLE INPUT
2
10
11

SAMPLE OUTPUT
Bob
Alice

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Susie listens to fairy tales before bed every day. Today's fairy tale was about wood cutters and the little girl immediately started imagining the choppers cutting wood. She imagined the situation that is described below.

There are *n* trees located along the road at points with coordinates *x*1,<=*x*2,<=...,<=*x**n*. Each tree has its height *h**i*. Woodcutters can cut down a tree and fell it to the left or to the right. After that it occupies one of the segments [*x**i*<=-<=*h**i*,<=*x**i*] or [*x**i*;*x**i*<=+<=*h**i*]. The tree that is not cut down occupies a single point with coordinate *x**i*. Woodcutters can fell a tree if the segment to be occupied by the fallen tree doesn't contain any occupied point. The woodcutters want to process as many trees as possible, so Susie wonders, what is the maximum number of trees to fell.

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

Next *n* lines contain pairs of integers *x**i*,<=*h**i* (1<=≤<=*x**i*,<=*h**i*<=≤<=109) — the coordinate and the height of the *і*-th tree.

The pairs are given in the order of ascending *x**i*. No two trees are located at the point with the same coordinate.

Output Specification:
Print a single number — the maximum number of trees that you can cut down by the given rules.

Demo Input:
['5\n1 2\n2 1\n5 10\n10 9\n19 1\n', '5\n1 2\n2 1\n5 10\n10 9\n20 1\n']

Demo Output:
['3\n', '4\n']

Note:
In the first sample you can fell the trees like that: 
 -  fell the 1-st tree to the left — now it occupies segment [ - 1;1] -  fell the 2-nd tree to the right — now it occupies segment [2;3] -  leave the 3-rd tree — it occupies point 5 -  leave the 4-th tree — it occupies point 10 -  fell the 5-th tree to the right — now it occupies segment [19;20] 
In the second sample you can also fell 4-th tree to the right, after that it will occupy segment [10;19].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Using roman numerals the numbers $1, 2, 3, 4, 5, 6, 7, 8, 9$ are written as ‘I’, ‘II’, ‘III’, ‘IV’, ‘V’, ‘VI’, ‘VII’, ‘VIII’, ‘IX’. The numbers $10, 20, 30, 40, 50, 60, 70, 80, 90$ are written as ‘X’, ‘XX’, ‘XXX’, ‘XL’, ‘L’, ‘LX’, ‘LXX’, ‘LXXX’, ‘XC’. Any number smaller than $100$ can be written by converting tens and ones separately and concatenating the results. So, for example, the number $48$ would be written as XLVIII, XL for $40$ and VIII for $8$. Given a number written in roman numerals, rearrange its characters so that you create the smallest possible number, written in roman numerals.

-----Input-----
The first and only line of input contains one integer $B$ ($1 \leq B < 100 $), written using roman numerals.

-----Output-----
The first and only line of output should contain a rearrangement of input characters so that it represents the smallest possible number, written in roman numerals.

-----Examples-----
Sample Input 1:
VII
Sample Output 1:
VII

Sample Input 2:
VI
Sample Output 2:
IV

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko found a wooden board and $N$ nails in his attic. Mirko hammered the nails into the board as fast as possible. The board can be modeled by a coordinate plane and the nails as points in it. No two nails have the same $x$- or the same $y$-coordinate.

In order to keep having fun, Mirko stole his sister’s elastic hair band, spread it over all nails and then let go. The elastic, naturally, tightened around the nails.

Mirko then repeats these steps while there are at least three nails in the board:
 - Write down the area of the shape enclosed by the hair band.
 - Picks the leftmost, rightmost, topmost or bottommost nail in the board.
 - Remove the chosen nail from the board; the elastic tightens again around the remaining nails.

Write a program that calculates the numbers written in step 1 of each iteration, if we know the nail Mirko picks in step 2 of each iteration.

-----Input-----
The first line contains the integer $N$ $(3 \leq N \leq 300000)$, the number of nails.

Each of the following $N$ lines contains two integers separated by a space, the coordinates of a nail. All coordinates will be between 1 and $1000000000$. No two nails will share the same $x$- or $y$-coordinate. The next line contains $N-2$ letters ’L’, ’R’, ’U’ or ’D’. The letters represent the nails Mirko picked in order:
 - ’L’ for the leftmost nail (smallest $x$-coordinate),
 - ’R’ for the rightmost nail (largest $x$-coordinate),
 - ’U’ for the topmost nail (largest $y$-coordinate),
 - ’D’ for the bottommost nail (smallest $y$-coordinate).

-----Output-----
Output $N-2$ numbers, each on a separate line. The numbers are, in order, the areas that Mirko wrote down. Output numbers with one digit after the decimal point.

-----Examples-----
Sample Input:
5
1 4
2 2
4 1
3 5
5 3
LUR
Sample Output:
9.0
6.5
2.5

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

The poly tool returns the coefficients of a polynomial with the given sequence of roots.

print numpy.poly([-1, 1, 1, 10])        #Output : [  1 -11   9  11 -10]

roots  

The roots tool returns the roots of a polynomial with the given coefficients.

print numpy.roots([1, 0, -1])           #Output : [-1.  1.]

polyint

The polyint tool returns an antiderivative (indefinite integral) of a polynomial.

print numpy.polyint([1, 1, 1])          #Output : [ 0.33333333  0.5         1.          0.        ]

polyder    

The polyder tool returns the derivative of the specified order of a polynomial.

print numpy.polyder([1, 1, 1, 1])       #Output : [3 2 1]

polyval

The polyval tool evaluates the polynomial at specific value.

print numpy.polyval([1, -2, 0, 2], 4)   #Output : 34

polyfit

The polyfit tool fits a polynomial of a specified order to a set of data using a least-squares approach.

print numpy.polyfit([0,1,-1, 2, -2], [0,1,1, 4, 4], 2)
#Output : [  1.00000000e+00   0.00000000e+00  -3.97205465e-16]

The functions polyadd, polysub, polymul, and polydiv also handle proper addition,
subtraction, multiplication, and division of polynomial coefficients, respectively.

Task  

You are given the coefficients of a polynomial $\mbox{P}$. 

Your task is to find the value of $\mbox{P}$ at point $\boldsymbol{x}$.

Input Format

The first line contains the space separated value of the coefficients in $\mbox{P}$. 

The second line contains the value of $\boldsymbol{x}$.

Output Format

Print the desired value.

Sample Input
1.1 2 3
0

Sample Output
3.0

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