vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Polycarp is sad — New Year is coming in few days but there is still no snow in his city. To bring himself New Year mood, he decided to decorate his house with some garlands.

The local store introduced a new service this year, called "Build your own garland". So you can buy some red, green and blue lamps, provide them and the store workers will solder a single garland of them. The resulting garland will have all the lamps you provided put in a line. Moreover, no pair of lamps of the same color will be adjacent to each other in this garland!

For example, if you provide $3$ red, $3$ green and $3$ blue lamps, the resulting garland can look like this: "RGBRBGBGR" ("RGB" being the red, green and blue color, respectively). Note that it's ok to have lamps of the same color on the ends of the garland.

However, if you provide, say, $1$ red, $10$ green and $2$ blue lamps then the store workers won't be able to build any garland of them. Any garland consisting of these lamps will have at least one pair of lamps of the same color adjacent to each other. Note that the store workers should use all the lamps you provided.

So Polycarp has bought some sets of lamps and now he wants to know if the store workers can build a garland from each of them.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of sets of lamps Polycarp has bought.

Each of the next $t$ lines contains three integers $r$, $g$ and $b$ ($1 \le r, g, b \le 10^9$) — the number of red, green and blue lamps in the set, respectively.


-----Output-----

Print $t$ lines — for each set of lamps print "Yes" if the store workers can build a garland from them and "No" otherwise.


-----Example-----
Input
3
3 3 3
1 10 2
2 1 1

Output
Yes
No
Yes



-----Note-----

The first two sets are desribed in the statement.

The third set produces garland "RBRG", for example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N integers 1, 2, 3, \ldots N are placed on a circle in clockwise order such that i and (i+1) are adjacent for all 1 ≤ i ≤ N - 1, and 1 and N are also adjacent.

Given an integer K, Ashish repeatedly removes integers from the circle until only one integer remains. He does so in the following manner. In each move, Ashish finds the integer which is on the K-th place from the smallest one in clockwise order and removes it from the circle, i.e. its neighbours now become adjacent.

For example, consider the case when N = 3 and K = 3. Let the circular array [1, 2, 3] denote the integers on the circle. In the first move, 3 is removed since it is the K-th integer starting from 1, which is the smallest integer currently on the circle. Likewise, in the next move 1 is removed and finally only 2 remains. [1, 2, \underline{3}] \rightarrow [\underline{1}, 2] \rightarrow [2].

Since N and K may be very large, Ashish cannot simulate the process himself. Help him find the parity of the last integer that remains after the repeated removals. In other words, report if this integer is odd or even.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two integers N and K.

------ Output Format ------ 

For each test case, output ODD if the last integer that remains after the repeated removals is odd, and EVEN otherwise.

Each letter of the output may be printed in either lowercase or uppercase. For example, the strings odd, Odd, and ODD will all be treated as equivalent.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{18}$
$1 ≤ K ≤ N$

----- Sample Input 1 ------ 
4
4 1
3 3
9 1
3489601027782 8104267
----- Sample Output 1 ------ 
EVEN
EVEN
ODD
EVEN
----- explanation 1 ------ 
Test case $1$: The last integer that remains is $4$, which is EVEN.

$[\underline{1}, 2, 3, 4] \rightarrow [\underline{2}, 3, 4] \rightarrow [\underline{3}, 4] \rightarrow [4]$

Test case $2$: The last integer that remains is $2$, which is EVEN.

$[1, 2, \underline{3}] \rightarrow [\underline{1}, 2] \rightarrow [2]$

Test case $3$: The last integer that remains is $9$, which is ODD.

$[\underline{1}, 2, 3, 4, 5, 6, 7, 8, 9] \rightarrow [\underline{2}, 3, 4, 5, 6, 7, 8, 9] \rightarrow \ldots \rightarrow [9]$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasiliy has an exam period which will continue for n days. He has to pass exams on m subjects. Subjects are numbered from 1 to m.

About every day we know exam for which one of m subjects can be passed on that day. Perhaps, some day you can't pass any exam. It is not allowed to pass more than one exam on any day. 

On each day Vasiliy can either pass the exam of that day (it takes the whole day) or prepare all day for some exam or have a rest. 

About each subject Vasiliy know a number a_{i} — the number of days he should prepare to pass the exam number i. Vasiliy can switch subjects while preparing for exams, it is not necessary to prepare continuously during a_{i} days for the exam number i. He can mix the order of preparation for exams in any way.

Your task is to determine the minimum number of days in which Vasiliy can pass all exams, or determine that it is impossible. Each exam should be passed exactly one time. 


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5) — the number of days in the exam period and the number of subjects. 

The second line contains n integers d_1, d_2, ..., d_{n} (0 ≤ d_{i} ≤ m), where d_{i} is the number of subject, the exam of which can be passed on the day number i. If d_{i} equals 0, it is not allowed to pass any exams on the day number i. 

The third line contains m positive integers a_1, a_2, ..., a_{m} (1 ≤ a_{i} ≤ 10^5), where a_{i} is the number of days that are needed to prepare before passing the exam on the subject i.


-----Output-----

Print one integer — the minimum number of days in which Vasiliy can pass all exams. If it is impossible, print -1.


-----Examples-----
Input
7 2
0 1 0 2 1 0 2
2 1

Output
5

Input
10 3
0 0 1 2 3 0 2 0 1 2
1 1 4

Output
9

Input
5 1
1 1 1 1 1
5

Output
-1



-----Note-----

In the first example Vasiliy can behave as follows. On the first and the second day he can prepare for the exam number 1 and pass it on the fifth day, prepare for the exam number 2 on the third day and pass it on the fourth day.

In the second example Vasiliy should prepare for the exam number 3 during the first four days and pass it on the fifth day. Then on the sixth day he should prepare for the exam number 2 and then pass it on the seventh day. After that he needs to prepare for the exam number 1 on the eighth day and pass it on the ninth day. 

In the third example Vasiliy can't pass the only exam because he hasn't anough time to prepare for it.

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 which are permutation of first n numbers.

You need to make both arrays magical.Two Arrays A and B are magical when for each valid position i, A[i] = B[i].

Operations allowed (only on array A) are
Salt: Change any number of array A to any number you wish with cost x.
Pepper: Rotate array A left by 1 position with cost y. i.e. 
change {A[1],A[2],A[3],...,A[n]} to {A[2],A[3],...A[n],A[1]} with cost y.

You need to print minimum cost to make both arrays magical.

Input Format:
First line contains T i.e. number of test cases. 1 ≤ T ≤ 25
First line of each test case contains N, size of array. 1 ≤ N ≤ 10^5
Second line contains two space separated integers x and y. 1 ≤ x ≤ 100 and 1 ≤ y ≤ 100
Third line contains n space separated integers where i'th integer = A[i]
Fourth line contains n space separated integers where i'th integer = B[i]
It is guaranteed that both array A and B are some permutation of first N Numbers. 

Output Format:
For each test case, print (minimum cost % 1000000007) in a single line without any spaces.

Author : Sumeet Varma

SAMPLE INPUT
2
2
3 4
1 2
2 1
4
3 5
1 2 3 4
2 3 4 1

SAMPLE OUTPUT
4
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Counting Kangaroos is Fun

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* kangaroos with pockets. Each kangaroo has a size (integer number). A kangaroo can go into another kangaroo's pocket if and only if the size of kangaroo who hold the kangaroo is at least twice as large as the size of kangaroo who is held.

Each kangaroo can hold at most one kangaroo, and the kangaroo who is held by another kangaroo cannot hold any kangaroos.

The kangaroo who is held by another kangaroo cannot be visible from outside. Please, find a plan of holding kangaroos with the minimal number of kangaroos who is visible.

Input Specification:
The first line contains a single integer — *n* (1<=≤<=*n*<=≤<=5·105). Each of the next *n* lines contains an integer *s**i* — the size of the *i*-th kangaroo (1<=≤<=*s**i*<=≤<=105).

Output Specification:
Output a single integer — the optimal number of visible kangaroos.

Demo Input:
['8\n2\n5\n7\n6\n9\n8\n4\n2\n', '8\n9\n1\n6\n2\n6\n5\n8\n3\n']

Demo Output:
['5\n', '5\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have *r* red, *g* green and *b* blue balloons. To decorate a single table for the banquet you need exactly three balloons. Three balloons attached to some table shouldn't have the same color. What maximum number *t* of tables can be decorated if we know number of balloons of each color?

Your task is to write a program that for given values *r*, *g* and *b* will find the maximum number *t* of tables, that can be decorated in the required manner.

Input Specification:
The single line contains three integers *r*, *g* and *b* (0<=≤<=*r*,<=*g*,<=*b*<=≤<=2·109) — the number of red, green and blue baloons respectively. The numbers are separated by exactly one space.

Output Specification:
Print a single integer *t* — the maximum number of tables that can be decorated in the required manner.

Demo Input:
['5 4 3\n', '1 1 1\n', '2 3 3\n']

Demo Output:
['4\n', '1\n', '2\n']

Note:
In the first sample you can decorate the tables with the following balloon sets: "rgg", "gbb", "brr", "rrg", where "r", "g" and "b" represent the red, green and blue balls, respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two integer sequences existed initially — one of them was strictly increasing, and the other one — strictly decreasing.

Strictly increasing sequence is a sequence of integers [x_1 < x_2 < ... < x_k]. And strictly decreasing sequence is a sequence of integers [y_1 > y_2 > ... > y_l]. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

They were merged into one sequence a. After that sequence a got shuffled. For example, some of the possible resulting sequences a for an increasing sequence [1, 3, 4] and a decreasing sequence [10, 4, 2] are sequences [1, 2, 3, 4, 4, 10] or [4, 2, 1, 10, 4, 3].

This shuffled sequence a is given in the input.

Your task is to find any two suitable initial sequences. One of them should be strictly increasing and the other one — strictly decreasing. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

If there is a contradiction in the input and it is impossible to split the given sequence a to increasing and decreasing sequences, print "NO".

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of elements in a.

The second line of the input contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 2 ⋅ 10^5), where a_i is the i-th element of a.

Output

If there is a contradiction in the input and it is impossible to split the given sequence a to increasing and decreasing sequences, print "NO" in the first line.

Otherwise print "YES" in the first line and any two suitable sequences. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

In the second line print n_i — the number of elements in the strictly increasing sequence. n_i can be zero, in this case the increasing sequence is empty.

In the third line print n_i integers inc_1, inc_2, ..., inc_{n_i} in the increasing order of its values (inc_1 < inc_2 < ... < inc_{n_i}) — the strictly increasing sequence itself. You can keep this line empty if n_i = 0 (or just print the empty line).

In the fourth line print n_d — the number of elements in the strictly decreasing sequence. n_d can be zero, in this case the decreasing sequence is empty.

In the fifth line print n_d integers dec_1, dec_2, ..., dec_{n_d} in the decreasing order of its values (dec_1 > dec_2 > ... > dec_{n_d}) — the strictly decreasing sequence itself. You can keep this line empty if n_d = 0 (or just print the empty line).

n_i + n_d should be equal to n and the union of printed sequences should be a permutation of the given sequence (in case of "YES" answer).

Examples

Input


7
7 2 7 3 3 1 4


Output


YES
2
3 7 
5
7 4 3 2 1 


Input


5
4 3 1 5 3


Output


YES
1
3 
4
5 4 3 1 


Input


5
1 1 2 1 2


Output


NO


Input


5
0 1 2 3 4


Output


YES
0

5
4 3 2 1 0 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pappu is confused between 6 & 9. He works in the billing department of abc company and his work is to return the remaining amount to the customers. If the actual remaining amount is given we need to find the maximum possible extra amount given by the pappu to the customers.
Example 1:
Input: amount = 56
Output: 3
Explanation: maximum possible extra 
             amount = 59 - 56 = 3.
Example 2:
Input: amount = 66
Output: 33
Explanation: maximum possible extra 
             amount = 99 - 66 = 33.
User Task:
Your task is to complete the function findDiff() which takes single argument(amount) and returns the answer. You need not take any input or print anything.
Expected Time Complexity: O(log_{10}amount).
Expected Auxiliary Space: O(log_{10}amount).
Constraints
1 ≤ N≤ 10000001

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imagine a city with n horizontal streets crossing m vertical streets, forming an (n - 1) × (m - 1) grid. In order to increase the traffic flow, mayor of the city has decided to make each street one way. This means in each horizontal street, the traffic moves only from west to east or only from east to west. Also, traffic moves only from north to south or only from south to north in each vertical street. It is possible to enter a horizontal street from a vertical street, or vice versa, at their intersection.

 [Image] 

The mayor has received some street direction patterns. Your task is to check whether it is possible to reach any junction from any other junction in the proposed street direction pattern.


-----Input-----

The first line of input contains two integers n and m, (2 ≤ n, m ≤ 20), denoting the number of horizontal streets and the number of vertical streets.

The second line contains a string of length n, made of characters '<' and '>', denoting direction of each horizontal street. If the i-th character is equal to '<', the street is directed from east to west otherwise, the street is directed from west to east. Streets are listed in order from north to south.

The third line contains a string of length m, made of characters '^' and 'v', denoting direction of each vertical street. If the i-th character is equal to '^', the street is directed from south to north, otherwise the street is directed from north to south. Streets are listed in order from west to east.


-----Output-----

If the given pattern meets the mayor's criteria, print a single line containing "YES", otherwise print a single line containing "NO".


-----Examples-----
Input
3 3
><>
v^v

Output
NO

Input
4 6
<><>
v^v^v^

Output
YES



-----Note-----

The figure above shows street directions in the second sample test case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Methodius received an email from his friend Polycarp. However, Polycarp's keyboard is broken, so pressing a key on it once may cause the corresponding symbol to appear more than once (if you press a key on a regular keyboard, it prints exactly one symbol).

For example, as a result of typing the word "hello", the following words could be printed: "hello", "hhhhello", "hheeeellllooo", but the following could not be printed: "hell", "helo", "hhllllooo".

Note, that when you press a key, the corresponding symbol must appear (possibly, more than once). The keyboard is broken in a random manner, it means that pressing the same key you can get the different number of letters in the result.

For each word in the letter, Methodius has guessed what word Polycarp actually wanted to write, but he is not sure about it, so he asks you to help him.

You are given a list of pairs of words. For each pair, determine if the second word could be printed by typing the first one on Polycarp's keyboard.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 10^5$) — the number of pairs to check. Further input contains $n$ descriptions of pairs.

The first line of each description contains a single non-empty word $s$ consisting of lowercase Latin letters. The second line of the description contains a single non-empty word $t$ consisting of lowercase Latin letters. The lengths of both strings are not greater than $10^6$.

It is guaranteed that the total length of all words $s$ in the input is not greater than $10^6$. Also, it is guaranteed that the total length of all words $t$ in the input is not greater than $10^6$.


-----Output-----

Output $n$ lines. In the $i$-th line for the $i$-th pair of words $s$ and $t$ print YES if the word $t$ could be printed by typing the word $s$. Otherwise, print NO.


-----Examples-----
Input
4
hello
hello
hello
helloo
hello
hlllloo
hello
helo

Output
YES
YES
NO
NO

Input
5
aa
bb
codeforces
codeforce
polycarp
poolycarpp
aaaa
aaaab
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxyz

Output
NO
NO
YES
NO
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N people living on a number line.
The i-th person lives at coordinate X_i.
You are going to hold a meeting that all N people have to attend.
The meeting can be held at any integer coordinate. If you choose to hold the meeting at coordinate P, the i-th person will spend (X_i - P)^2 points of stamina to attend the meeting.
Find the minimum total points of stamina the N people have to spend.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 100
 - 1 \leq X_i \leq 100

-----Input-----
Input is given from Standard Input in the following format:
N
X_1 X_2 ... X_N

-----Output-----
Print the minimum total stamina the N people have to spend.

-----Sample Input-----
2
1 4

-----Sample Output-----
5

Assume the meeting is held at coordinate 2. In this case, the first person will spend (1 - 2)^2 points of stamina, and the second person will spend (4 - 2)^2 = 4 points of stamina, for a total of 5 points of stamina. This is the minimum total stamina that the 2 people have to spend.
Note that you can hold the meeting only at an integer coordinate.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Nina is learning to read. Her favorite letter is N, and she looks for it everywhere.

There is a set of $N$ points on the plane. Let's consider four different points from the set and name them $\mbox{A}$, $\mbox{B}$, $\mbox{C}$, and $\mbox{D}$ (in that order). Nina says that these four points form the letter N if all the following conditions are met:

$\mbox{A}$ is located strictly to the right of ray $\overrightarrow{BC}$ (in this order).
$\mbox{D}$ is located strictly to the left of ray $\overrightarrow{BC}$ (in this order).
Angle $\angle ABC\leq90^{\circ}$ 
Angle $\angle BCD\leq90\text{°}$

How many Ns can she find? We consider letters to be sets of four points, and two letters differ if the value of one or more of the points (i.e., $A,B,C$, or $\mbox{D}$) differs between the two corresponding sets of points. For example, if two sets of points have differing $\mbox{A}$ values, then they are different letters. In addition, letters that can be transformed into each other only by reversing point order are considered to be the same letter. 

Input Format

The first line contains a single integer, $N$, denoting the number of points. 

Each line $\boldsymbol{i}$ of the $N$ subsequent lines contain two space-separated integers, $x_i$ and $y_i$, describing the respective coordinates of point $(x_i,y_i)$. No two points coincide.

Constraints

$4\leq N\leq2318$
$-10^4\leq x_i,y_i\leq10^4$

Output Format

Print a single integer denoting the number of different Ns.

Sample Input
4
0 0
0 2
2 0
2 2

Sample Output
2

Explanation

To make this easier to read, we'll label our points as $P_1=(0,0)$, $P_2=(0,2)$, $P_3=(2,0)$, and $P_4=(2,2)$.

There are two different letter Ns:

$A,B,C,D=\{P_1,P_2,P_3,P_4\}$
$A,B,C,D=\{P_2,P_4,P_1,P_3\}$

Sets $\{P_1,P_3,P_2,P_4\}$ and $\{P_2,P_1,P_4,P_3\}$ (as well as their reversed variants) don't meet conditions $1$ and $2$ (we get a reversed N, like the Russian letter И).

Sets $\{P_4,P_3,P_2,P_1\}$ and $\{P_3,P_1,P_4,P_2\}$ are reversed variants of $1$ and $2$, so we don't add them to our answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Julia is going to cook a chicken in the kitchen of her dormitory. To save energy, the stove in the kitchen automatically turns off after k minutes after turning on.

During cooking, Julia goes to the kitchen every d minutes and turns on the stove if it is turned off. While the cooker is turned off, it stays warm. The stove switches on and off instantly.

It is known that the chicken needs t minutes to be cooked on the stove, if it is turned on, and 2t minutes, if it is turned off. You need to find out, how much time will Julia have to cook the chicken, if it is considered that the chicken is cooked evenly, with constant speed when the stove is turned on and at a constant speed when it is turned off.


-----Input-----

The single line contains three integers k, d and t (1 ≤ k, d, t ≤ 10^18).


-----Output-----

Print a single number, the total time of cooking in minutes. The relative or absolute error must not exceed 10^{ - 9}.

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


-----Examples-----
Input
3 2 6

Output
6.5

Input
4 2 20

Output
20.0



-----Note-----

In the first example, the chicken will be cooked for 3 minutes on the turned on stove, after this it will be cooked for $\frac{3}{6}$. Then the chicken will be cooked for one minute on a turned off stove, it will be cooked for $\frac{1}{12}$. Thus, after four minutes the chicken will be cooked for $\frac{3}{6} + \frac{1}{12} = \frac{7}{12}$. Before the fifth minute Julia will turn on the stove and after 2.5 minutes the chicken will be ready $\frac{7}{12} + \frac{2.5}{6} = 1$.

In the second example, when the stove is turned off, Julia will immediately turn it on, so the stove will always be turned on and the chicken will be cooked in 20 minutes.

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