vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are famous Russian nesting dolls named matryoshkas sold in one of the souvenir stores nearby, and you'd like to buy several of them. The store has $n$ different matryoshkas. Any matryoshka is a figure of volume $out_i$ with an empty space inside of volume $in_i$ (of course, $out_i > in_i$).

You don't have much free space inside your bag, but, fortunately, you know that matryoshkas can be nested one inside another. Formally, let's call a set of matryoshkas nested if we can rearrange dolls in such a way, that the first doll can be nested inside the second one, the second doll — inside the third one and so on. Matryoshka $i$ can be nested inside matryoshka $j$ if $out_i \le in_j$. So only the last doll will take space inside your bag.

Let's call extra space of a nested set of dolls as a total volume of empty space inside this structure. Obviously, it's equal to $in_{i_1} + (in_{i_2} - out_{i_1}) + (in_{i_3} - out_{i_2}) + \dots + (in_{i_k} - out_{i_{k-1}})$, where $i_1$, $i_2$, ..., $i_k$ are the indices of the chosen dolls in the order they are nested in each other.

Finally, let's call a nested subset of the given sequence as big enough if there isn't any doll from the sequence that can be added to the nested subset without breaking its nested property.

You want to buy many matryoshkas, so you should choose a big enough nested subset to buy it. But you will be disappointed if too much space in your bag will be wasted, so you want to choose a big enough subset so that its extra space is minimum possible among all big enough subsets. Now you wonder, how many different nested subsets meet these conditions (they are big enough, and there is no big enough subset such that its extra space is less than the extra space of the chosen subset). Two subsets are considered different if there exists at least one index $i$ such that one of the subsets contains the $i$-th doll, and another subset doesn't.

Since the answer can be large, print it modulo $10^9 + 7$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of matryoshkas.

The next $n$ lines contain a description of each doll: two integers $out_i$ and $in_i$ ($1 \le in_i < out_i \le 10^9$) — the outer and inners volumes of the $i$-th matryoshka.


-----Output-----

Print one integer — the number of big enough nested subsets such that extra space of each of these subsets is minimum possible. Since the answer can be large, print it modulo $10^9 + 7$.


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

Output
6



-----Note-----

There are $6$ big enough nested subsets with minimum possible extra space in the example:   $\{1, 5\}$: we can't add any other matryoshka and keep it nested; it's extra space is $1$;  $\{1, 6\}$;  $\{2, 4, 5\}$;  $\{2, 4, 6\}$;  $\{3, 4, 5\}$;  $\{3, 4, 6\}$. 

There are no more "good" subsets because, for example, subset $\{6, 7\}$ is not big enough (we can add the $4$-th matryoshka to it) or subset $\{4, 6, 7\}$ has extra space equal to $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chester Bennington, being a skinny kid as we all know, is always bullied since he was a child. This time its just unacceptable. Mike Shinoda, the second vocalist to his band, tried to bully him. Chester was never a bright student and Mike, being a high school graduate, gave him a tough mathematical problem. He gave Chester a number N. His task is to find all the prime numbers under N(inclusive) which can be written as the sum of two primes and list them.

Help Chester so that this time he is not bullied....... Again !!!

Input: First line contains t, the number of test cases. t lines follow after that which contain an integer N.

Output: For each test case, you have to print all the prime numbers that meet the above mentioned condition in a single line in a space separated format. For each test-case use a new line.

Constraints:

1 ≤ t ≤ 100

1 ≤ N ≤ 10000

Note: 1 and 0 are not considered Primes

Problem Setter: Rohit Mishra

SAMPLE INPUT
3
7
17
29

SAMPLE OUTPUT
5 7
5 7 13
5 7 13 19

Explanation

Consider test case - 2
N=17
Prime Numbers under 17 are 2,3,5,7,11,13,17
Output is 5,7,13

As 1+10 = 2+9 = 3+8 = 4+7 = 5+6 = 11
None of the above mentioned pairs meets the required criteria.
Same is the case with the other numbers which are not mentioned in the output.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Function Descriptions=====
itertools.permutations(iterable[, r])

This tool returns successive rlength permutations of elements in an iterable.
If r is not specified or is None, then r defaults to the length of the iterable, and all possible full length permutations are generated.
Permutations are printed in a lexicographic sorted order. So, if the input iterable is sorted, the permutation tuples will be produced in a sorted order.

Sample Code
>>> from itertools import permutations
>>> print permutations(['1','2','3'])
<itertools.permutations object at 0x02A45210>
>>> 
>>> print list(permutations(['1','2','3']))
[('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'), ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')]
>>> 
>>> print list(permutations(['1','2','3'],2))
[('1', '2'), ('1', '3'), ('2', '1'), ('2', '3'), ('3', '1'), ('3', '2')]
>>>
>>> print list(permutations('abc',3))
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

=====Problem Statement=====
You are given a string S.
Your task is to print all possible permutations of size k of the string in lexicographic sorted order.

=====Input Format=====
A single line containing the space separated string S and the integer value k.

=====Output Format=====
Print the permutations of the string S on separate lines.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Make the 2D list by the sequential integers started by the ```head``` number.

See the example test cases for the expected output.

``` 
Note:

-10**20 < the head number <10**20
1 <=  the number of rows <= 1000
0 <=  the number of columms <= 1000
```

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
As you must know, the maximum clique problem in an arbitrary graph is *NP*-hard. Nevertheless, for some graphs of specific kinds it can be solved effectively.

Just in case, let us remind you that a clique in a non-directed graph is a subset of the vertices of a graph, such that any two vertices of this subset are connected by an edge. In particular, an empty set of vertexes and a set consisting of a single vertex, are cliques.

Let's define a divisibility graph for a set of positive integers *A*<==<={*a*1,<=*a*2,<=...,<=*a**n*} as follows. The vertices of the given graph are numbers from set *A*, and two numbers *a**i* and *a**j* (*i*<=≠<=*j*) are connected by an edge if and only if either *a**i* is divisible by *a**j*, or *a**j* is divisible by *a**i*.

You are given a set of non-negative integers *A*. Determine the size of a maximum clique in a divisibility graph for set *A*.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=106), that sets the size of set *A*.

The second line contains *n* distinct positive integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=106) — elements of subset *A*. The numbers in the line follow in the ascending order.

Output Specification:
Print a single number — the maximum size of a clique in a divisibility graph for set *A*.

Demo Input:
['8\n3 4 6 8 10 18 21 24\n']

Demo Output:
['3\n']

Note:
In the first sample test a clique of size 3 is, for example, a subset of vertexes {3, 6, 18}. A clique of a larger size doesn't exist in this graph.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Conan and Agasa play a Card Game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Edogawa Conan got tired of solving cases, and invited his friend, Professor Agasa, over. They decided to play a game of cards. Conan has *n* cards, and the *i*-th card has a number *a**i* written on it.

They take turns playing, starting with Conan. In each turn, the player chooses a card and removes it. Also, he removes all cards having a number strictly lesser than the number on the chosen card. Formally, if the player chooses the *i*-th card, he removes that card and removes the *j*-th card for all *j* such that *a**j*<=&lt;<=*a**i*.

A player loses if he cannot make a move on his turn, that is, he loses if there are no cards left. Predict the outcome of the game, assuming both players play optimally.

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

The next line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=105), where *a**i* is the number on the *i*-th card.

Output Specification:
If Conan wins, print "Conan" (without quotes), otherwise print "Agasa" (without quotes).

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

Demo Output:
['Conan\n', 'Agasa\n']

Note:
In the first example, Conan can just choose the card having number 7 on it and hence remove all the cards. After that, there are no cards left on Agasa's turn.

In the second example, no matter which card Conan chooses, there will be one one card left, which Agasa can choose. After that, there are no cards left when it becomes Conan's turn again.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* cities located along the one-way road. Cities are numbered from 1 to *n* in the direction of the road.

The *i*-th city had produced *p**i* units of goods. No more than *s**i* units of goods can be sold in the *i*-th city.

For each pair of cities *i* and *j* such that 1<=≤<=*i*<=&lt;<=*j*<=≤<=*n* you can no more than once transport no more than *c* units of goods from the city *i* to the city *j*. Note that goods can only be transported from a city with a lesser index to the city with a larger index. You can transport goods between cities in any order.

Determine the maximum number of produced goods that can be sold in total in all the cities after a sequence of transportations.

Input Specification:
The first line of the input contains two integers *n* and *c* (1<=≤<=*n*<=≤<=10<=000, 0<=≤<=*c*<=≤<=109) — the number of cities and the maximum amount of goods for a single transportation.

The second line contains *n* integers *p**i* (0<=≤<=*p**i*<=≤<=109) — the number of units of goods that were produced in each city.

The third line of input contains *n* integers *s**i* (0<=≤<=*s**i*<=≤<=109) — the number of units of goods that can be sold in each city.

Output Specification:
Print the maximum total number of produced goods that can be sold in all cities after a sequence of transportations.

Demo Input:
['3 0\n1 2 3\n3 2 1\n', '5 1\n7 4 2 1 0\n1 2 3 4 5\n', '4 3\n13 10 7 4\n4 7 10 13\n']

Demo Output:
['4\n', '12\n', '34\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given two arrays $a[1 \dots n]$ and $b[1 \dots n]$, both of the same length $n$.

In order to perform a push operation, you have to choose three integers $l, r, k$ satisfying $1 \le l \le r \le n$ and $k > 0$. Then, you will add $k$ to elements $a_l, a_{l+1}, \ldots, a_r$.

For example, if $a = [3, 7, 1, 4, 1, 2]$ and you choose $(l = 3, r = 5, k = 2)$, the array $a$ will become $[3, 7, \underline{3, 6, 3}, 2]$.

You can do this operation at most once. Can you make array $a$ equal to array $b$?

(We consider that $a = b$ if and only if, for every $1 \le i \le n$, $a_i = b_i$)


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 20$) — the number of test cases in the input.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100\ 000$) — the number of elements in each array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 1000$).

The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 1000$).

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

For each test case, output one line containing "YES" if it's possible to make arrays $a$ and $b$ equal by performing at most once the described operation or "NO" if it's impossible.

You can print each letter in any case (upper or lower).


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

Output
YES
NO
YES
NO



-----Note-----

The first test case is described in the statement: we can perform a push operation with parameters $(l=3, r=5, k=2)$ to make $a$ equal to $b$.

In the second test case, we would need at least two operations to make $a$ equal to $b$.

In the third test case, arrays $a$ and $b$ are already equal.

In the fourth test case, it's impossible to make $a$ equal to $b$, because the integer $k$ has to be positive.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given string s containing characters as integers only, the task is to delete all characters of this string in a minimum number of steps wherein one step you can delete the substring which is a palindrome. After deleting a substring remaining parts are concatenated.
Example 1:
Input: s = "2553432"
Output: 2
Explanation: In first step remove "55", 
then string becomes "23432" which is a 
palindrome.
Example 2:
Input: s = "1234"
Output: 4
Explanation: Remove each character in 
each step
Your Task:  
You don't need to read input or print anything. Complete the function minStepToDeleteString() which string s as input parameters and returns the integer value
Expected Time Complexity: O(|s|^{3})
Expected Auxiliary Space: O(|s|^{2})
Constraints:
1 ≤ |s| ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a student looking for a job. Today you had an employment examination for an IT company. They asked you to write an efficient program to perform several operations. First, they showed you an N \times N square matrix and a list of operations. All operations but one modify the matrix, and the last operation outputs the character in a specified cell. Please remember that you need to output the final matrix after you finish all the operations.

Followings are the detail of the operations:

WR r c v
(Write operation) write a integer v into the cell (r,c) (1 \leq v \leq 1,000,000)
CP r1 c1 r2 c2
(Copy operation) copy a character in the cell (r1,c1) into the cell (r2,c2)
SR r1 r2
(Swap Row operation) swap the r1-th row and r2-th row
SC c1 c2
(Swap Column operation) swap the c1-th column and c2-th column
RL
(Rotate Left operation) rotate the whole matrix in counter-clockwise direction by 90 degrees
RR
(Rotate Right operation) rotate the whole matrix in clockwise direction by 90 degrees
RH
(Reflect Horizontal operation) reverse the order of the rows
RV
(Reflect Vertical operation) reverse the order of the columns



Input

First line of each testcase contains nine integers. First two integers in the line, N and Q, indicate the size of matrix and the number of queries, respectively (1 \leq N,Q \leq 40,000). Next three integers, A B, and C, are coefficients to calculate values in initial matrix (1 \leq A,B,C \leq 1,000,000), and they are used as follows: A_{r,c} = (r * A + c * B) mod C where r and c are row and column indices, respectively (1\leq r,c\leq N). Last four integers, D, E, F, and G, are coefficients to compute the final hash value mentioned in the next section (1 \leq D \leq E \leq N, 1 \leq F \leq G \leq N, E - D \leq 1,000, G - F \leq 1,000). Each of next Q lines contains one operation in the format as described above.

Output

Output a hash value h computed from the final matrix B by using following pseudo source code.


h <- 314159265
for r = D...E
for c = F...G
h <- (31 * h + B_{r,c}) mod 1,000,000,007


where "<-" is a destructive assignment operator, "for i = S...T" indicates a loop for i from S to T (both inclusive), and "mod" is a remainder operation.

Examples

Input

2 1 3 6 12 1 2 1 2
WR 1 1 1


Output

676573821


Input

2 1 3 6 12 1 2 1 2
RL


Output

676636559


Input

2 1 3 6 12 1 2 1 2
RH


Output

676547189


Input

39989 6 999983 999979 999961 1 1000 1 1000
SR 1 39989
SC 1 39989
RL
RH
RR
RV


Output

458797120

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Archimedes is the name of a new 2D video game, which is very simple: the player hits start, at which point their avatar moves along an Archimedean spiral starting from the origin. When they hit a button, the avatar detaches from the spiral in the direction it is currently moving. The goal is to hit a target. The avatar’s path after it detaches must not intersect with any part of the spiral.

To help study this game, you’re asked to write a program that given the spiral’s angular velocity computes the point at which the player would need to press the button to release the avatar from the spiral in order to hit the target.

An Archimedean spiral is created when a point moves with constant velocity along a line that rotates with constant angular velocity around the origin. When expressed in polar coordinates $(r, \phi )$, an Archimedean spiral has a simple formulation: $r = b \ \phi $ where $r$ is the distance from the origin and $\phi $ is the angle between the point, origin, and the unit vector $(1, 0)$. $b$ is a constant that determines the distance between successive rings of the spiral.

-----Input-----
The input consists of a single line with $3$ real numbers $b$, $t_ x$, and $t_ y$, denoting the parameter $b$ ($0.01 \le b \le 10$) of the spiral described by $r = b \ \phi $ and the $x, y$ coordinates of the target $T = (t_ x, t_ y)$, restricted by $-10000 \le t_ x, t_ y \le 10000$. It is guaranteed that $\sqrt{t_ x^2+t_ y^2} > 2 \pi b$, i.e., the avatar will stay on the spiral for at least one full $360$ degree turn. It is also guaranteed that the distance from point $T$ to the closest point on the spiral will be greater than $10^{-3}$. There may be up to $12$ significant digits in $b$, and up to $3$ digits after the decimal point in $t_ x$ and $t_ y$.

-----Output-----
Output the $x, y$ coordinates of the point on the spiral where the avatar should leave the spiral, continue in the direction it is moving, and hit the target without intersecting the spiral.

Your answer will be considered correct if the absolute or relative error of both $x$ and $y$ does not exceed $10^{-5}$.

-----Examples-----
Sample Input 1:
0.5 -5.301 3.098
Sample Output 1:
-1.26167861 3.88425357

Sample Input 2:
0.5 8 8
Sample Output 2:
9.21068947 2.56226688

Sample Input 3:
1 8 8
Sample Output 3:
6.22375968 -0.31921472

Sample Input 4:
0.5 -8 8
Sample Output 4:
-4.36385220 9.46891588

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya and Vasya decided to play a game. They have n cards (n is an even number). A single integer is written on each card.

Before the game Petya will choose an integer and after that Vasya will choose another integer (different from the number that Petya chose). During the game each player takes all the cards with number he chose. For example, if Petya chose number 5 before the game he will take all cards on which 5 is written and if Vasya chose number 10 before the game he will take all cards on which 10 is written.

The game is considered fair if Petya and Vasya can take all n cards, and the number of cards each player gets is the same.

Determine whether Petya and Vasya can choose integer numbers before the game so that the game is fair. 

Input

The first line contains a single integer n (2 ≤ n ≤ 100) — number of cards. It is guaranteed that n is an even number.

The following n lines contain a sequence of integers a1, a2, ..., an (one integer per line, 1 ≤ ai ≤ 100) — numbers written on the n cards.

Output

If it is impossible for Petya and Vasya to choose numbers in such a way that the game will be fair, print "NO" (without quotes) in the first line. In this case you should not print anything more.

In the other case print "YES" (without quotes) in the first line. In the second line print two distinct integers — number that Petya should choose and the number that Vasya should choose to make the game fair. If there are several solutions, print any of them.

Examples

Input

4
11
27
27
11


Output

YES
11 27


Input

2
6
6


Output

NO


Input

6
10
20
30
20
10
20


Output

NO


Input

6
1
1
2
2
3
3


Output

NO

Note

In the first example the game will be fair if, for example, Petya chooses number 11, and Vasya chooses number 27. Then the will take all cards — Petya will take cards 1 and 4, and Vasya will take cards 2 and 3. Thus, each of them will take exactly two cards.

In the second example fair game is impossible because the numbers written on the cards are equal, but the numbers that Petya and Vasya should choose should be distinct.

In the third example it is impossible to take all cards. Petya and Vasya can take at most five cards — for example, Petya can choose number 10 and Vasya can choose number 20. But for the game to be fair it is necessary to take 6 cards.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob has n heap(s) of gravel (initially there are exactly c piece(s) in each). He wants to do m operation(s) with that heaps, each maybe:

- adding pieces of gravel onto the heaps from u to v, exactly k pieces for each,
- or querying "how many pieces of gravel are there in the heap p now?".

-----Request-----
Help Bob do operations of the second type.

-----Input-----

- The first line contains the integers n,m,c, respectively.
- m following lines, each forms:

- S u v k to describe an operation of the first type.
- Q p to describe an operation of the second type.
(Each integer on a same line, or between the characters S, Q and the integers is separated by at least one space character)

-----Output-----
For each operation of the second type, output (on a single line) an integer answering to the respective query (follows the respective Input order).

-----Example-----Input:
7 5 0
Q 7
S 1 7 1
Q 3
S 1 3 1
Q 3
Output:
0
1
2

-----Limitations-----
- 0<n≤106
- 0<m≤250 000
- 0<u≤v≤n
- 0≤c,k≤109
- 0<p≤n

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