vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Taro made a sugoroku so that everyone can play at the children's association event. In order to make the game interesting, I wrote instructions such as "advance 6" and "back 5" in some of the sugoroku squares other than "Furidashi" and "Agari". Turn the roulette wheel to advance as many times as you can, and if an instruction is written on the stopped square, move according to that instruction. However, it does not follow the instructions of the squares that proceeded according to the instructions.

Roulette shall be able to give a number between 1 and a certain number with equal probability. Also, if you get a larger number than you reach "Agari", or if you follow the instructions and you go beyond "Agari", you will move to "Agari". If you follow the instructions and return before "Furidashi", you will return to "Furidashi".

<image>


However, depending on the instructions of the roulette wheel and the square, it may not be possible to reach the "rise". For example, let's say you made a sugoroku like the one shown in the figure. If you use a roulette wheel that only gives 1 and 2, you can go to "Agari" if you come out in the order of 1 and 2, but if you get 2 first, you will not be able to reach "Agari" forever no matter what comes out. Taro didn't know that and wrote instructions in various squares.

Therefore, on behalf of Taro, please create a program to determine whether or not you may not be able to reach the "rise" depending on the instructions of the roulette and the square.



input

The input consists of multiple datasets. The end of the input is indicated by a single zero line. Each dataset is given in the following format.


max
n
d1
d2
..
..
..
dn


The first line gives the maximum number of roulette wheels max (2 ≤ max ≤ 250), and the second line gives the number of cells other than "starting" and "rising" n (2 ≤ n ≤ 250). .. The next n lines are given the number di (-n ≤ di ≤ n) that represents the indication for each cell. When di is zero, it means that no instruction is written, when it is a positive number, it means | di | forward instruction, and when it is negative, it means | di | back instruction (where | x | is x). Represents an absolute value). All values ​​entered are integers.

The number of datasets does not exceed 100.

output

The judgment result is output to one line for each data set. Depending on the instructions of the roulette and the square, if it may not be possible to reach the "go up", "NG" is output, otherwise "OK" is output.

Example

Input

3
3
-2
1
0
2
4
2
0
-1
-2
2
2
-2
-2
0


Output

OK
NG
NG

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of n integer numbers a_0, a_1, ..., a_{n} - 1. Find the distance between two closest (nearest) minimums in it. It is guaranteed that in the array a minimum occurs at least two times.


-----Input-----

The first line contains positive integer n (2 ≤ n ≤ 10^5) — size of the given array. The second line contains n integers a_0, a_1, ..., a_{n} - 1 (1 ≤ a_{i} ≤ 10^9) — elements of the array. It is guaranteed that in the array a minimum occurs at least two times.


-----Output-----

Print the only number — distance between two nearest minimums in the array.


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

Output
1

Input
3
5 6 5

Output
2

Input
9
2 1 3 5 4 1 2 3 1

Output
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Emuskald needs a fence around his farm, but he is too lazy to build it himself. So he purchased a fence-building robot.

He wants the fence to be a regular polygon. The robot builds the fence along a single path, but it can only make fence corners at a single angle a.

Will the robot be able to build the fence Emuskald wants? In other words, is there a regular polygon which angles are equal to a?


-----Input-----

The first line of input contains an integer t (0 < t < 180) — the number of tests. Each of the following t lines contains a single integer a (0 < a < 180) — the angle the robot can make corners at measured in degrees.


-----Output-----

For each test, output on a single line "YES" (without quotes), if the robot can build a fence Emuskald wants, and "NO" (without quotes), if it is impossible.


-----Examples-----
Input
3
30
60
90

Output
NO
YES
YES



-----Note-----

In the first test case, it is impossible to build the fence, since there is no regular polygon with angle $30^{\circ}$.

In the second test case, the fence is a regular triangle, and in the last test case — a square.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kirti likes 8. Kirti's restaurant has many menus whose prices are multiples of 8. Now, Kirti has some digits written on a wooden board, and she'd like to cut the board to display prices in a new menu. In how many ways can Kirti choose consecutive digits from the board which denote integer multiples of 8?

In this problem, an integer must not have leading zeros. For example, 0, 8, 48, 1000 are integer multiples of 8, but 00, 5, 58, 01000 are not. 

INPUT

An input contains a string S, which denotes digits written on the wooden board. 

OUTPUT

Print the number of ways in which Kirti can choose consecutive digits which denote integer multiples of 8. 

CONSTRAINTS

1 ≤ |S| ≤ 1000000 (106), where |S| means the length of S.

S doesn't contain non-digit charactors.

SAMPLE INPUT
5858

SAMPLE OUTPUT
2

Explanation

Kirti can choose 5, 8, 5, 8, 58, 85, 58, 585, 858 and 5858. Here, only 8 and 8 are multiples of 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N bags, each containing two white balls. The i-th box contains two balls with integers x_i and y_i written on them, respectively.
For each of these bags, you will paint one of the balls red, and paint the other blue.
Afterwards, the 2N balls will be classified according to color.
Then, we will define the following:
 - R_{max}: the maximum integer written on a ball painted in red
 - R_{min}: the minimum integer written on a ball painted in red
 - B_{max}: the maximum integer written on a ball painted in blue
 - B_{min}: the minimum integer written on a ball painted in blue
Find the minimum possible value of (R_{max} - R_{min}) \times (B_{max} - B_{min}).

-----Constraints-----
 - 1 ≤ N ≤ 200,000
 - 1 ≤ x_i, y_i ≤ 10^9

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
:
x_N y_N

-----Output-----
Print the minimum possible value.

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

-----Sample Output-----
15

The optimal solution is to paint the balls with x_1, x_2, y_3 red, and paint the balls with y_1, y_2, x_3 blue.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An encoder encodes the first $16$ lowercase English letters using $4$ bits each. The first bit (from the left) of the code is $0$ if the letter lies among the first $8$ letters, else it is $1$, signifying that it lies among the last $8$ letters. The second bit of the code is $0$ if the letter lies among the first $4$ letters of those $8$ letters found in the previous step, else it's $1$, signifying that it lies among the last $4$ letters of those $8$ letters. Similarly, the third and the fourth bit each signify the half in which the letter lies. 
For example, the letter $j$ would be encoded as :
- Among $(a,b,c,d,e,f,g,h$ $|$ $i,j,k,l,m,n,o,p)$, $j$ appears in the second half. So the first bit of its encoding is $1$.
- Now, among $(i,j,k,l$ $|$ $m,n,o,p)$, $j$ appears in the first half. So the second bit of its encoding is $0$.
- Now, among $(i,j$ $|$ $k,l)$, $j$ appears in the first half. So the third bit of its encoding is $0$.
- Now, among $(i$ $|$ $j)$, $j$ appears in the second half. So the fourth and last bit of its encoding is $1$.
So $j$'s encoding is $1001$,
Given a binary encoded string $S$, of length at most $10^5$, decode the string. That is, the first 4 bits are the encoding of the first letter of the secret message, the next 4 bits encode the second letter, and so on. It is guaranteed that the string's length is a multiple of 4.

-----Input:-----
- The first line of the input contains an integer $T$, denoting the number of test cases.
- The first line of each test case contains an integer $N$, the length of the encoded string.
- The second line of each test case contains the encoded string $S$.

-----Output:-----
For each test case, print the decoded string, in a separate line.

-----Constraints-----
- $1 \leq T \leq 10$
- $4 \leq N \leq 10^5$
- The length of the encoded string is a multiple of $4$.
- $0 \le S_i \le 1$

-----Subtasks-----
- $100$ points : Original constraints. 

-----Sample Input:-----
3
4
0000
8
00001111
4
1001

-----Sample Output:-----
a
ap
j

-----Explanation:-----
- Sample Case $1$ : 
The first bit is $0$, so the letter lies among the first $8$ letters, i.e., among $a,b,c,d,e,f,g,h$. The second bit is $0$, so it lies among the first four of these, i.e., among $a,b,c,d$. 
The third bit is $0$, so it again lies in the first half, i.e., it's either $a$ or $b$. Finally, the fourth bit is also $0$, so we know that the letter is $a$.
- Sample Case $2$ : 
Each four bits correspond to a character. Just like in sample case $1$, $0000$ is equivalent to $a$. Similarly, $1111$ is equivalent to $p$. So, the decoded string is $ap$.
- Sample Case $3$ : 
The first bit is $1$, so the letter lies among the last $8$ letters, i.e., among $i,j,k,l,m,n,o,p$. The second bit is $0$, so it lies among the first four of these, i.e., among $i,j,k,l$. 
The third bit is $0$, so it again lies in the first half, i.e., it's either $i$ or $j$. Finally, the fourth bit is $1$, so we know that the letter is $j$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got another problem dealing with arrays. Let's consider an arbitrary sequence containing *n* (not necessarily different) integers *a*1, *a*2, ..., *a**n*. We are interested in all possible pairs of numbers (*a**i*, *a**j*), (1<=≤<=*i*,<=*j*<=≤<=*n*). In other words, let's consider all *n*2 pairs of numbers, picked from the given array.

For example, in sequence *a*<==<={3,<=1,<=5} are 9 pairs of numbers: (3,<=3),<=(3,<=1),<=(3,<=5),<=(1,<=3),<=(1,<=1),<=(1,<=5),<=(5,<=3),<=(5,<=1),<=(5,<=5).

Let's sort all resulting pairs lexicographically by non-decreasing. Let us remind you that pair (*p*1, *q*1) is lexicographically less than pair (*p*2, *q*2) only if either *p*1 &lt; *p*2, or *p*1 = *p*2 and *q*1 &lt; *q*2.

Then the sequence, mentioned above, will be sorted like that: (1,<=1),<=(1,<=3),<=(1,<=5),<=(3,<=1),<=(3,<=3),<=(3,<=5),<=(5,<=1),<=(5,<=3),<=(5,<=5)

Let's number all the pair in the sorted list from 1 to *n*2. Your task is formulated like this: you should find the *k*-th pair in the ordered list of all possible pairs of the array you've been given.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=105,<=1<=≤<=*k*<=≤<=*n*2). The second line contains the array containing *n* integers *a*1, *a*2, ..., *a**n* (<=-<=109<=≤<=*a**i*<=≤<=109). The numbers in the array can coincide. All numbers are separated with spaces.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout, streams or the %I64d specificator instead.

Output Specification:
In the single line print two numbers — the sought *k*-th pair.

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

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

Note:
In the first sample the sorted sequence for the given array looks as: (1, 1), (1, 2), (2, 1), (2, 2). The 4-th of them is pair (2, 2).

The sorted sequence for the array from the second sample is given in the statement. The 2-nd pair there is (1, 3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a set S of N points in a two-dimensional plane. The coordinates of the i-th point are (x_i, y_i). The N points have distinct x-coordinates and distinct y-coordinates.

For a non-empty subset T of S, let f(T) be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in T. More formally, we define f(T) as follows:

* f(T) :=  (the number of integers i (1 \leq i \leq N) such that a \leq x_i \leq b and c \leq y_i \leq d, where a, b, c, and d are the minimum x-coordinate, the maximum x-coordinate, the minimum y-coordinate, and the maximum y-coordinate of the points in T)



Find the sum of f(T) over all non-empty subset T of S. Since it can be enormous, print the sum modulo 998244353.

Constraints

* 1 \leq N \leq 2 \times 10^5
* -10^9 \leq x_i, y_i \leq 10^9
* x_i \neq x_j (i \neq j)
* y_i \neq y_j (i \neq j)
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
x_1 y_1
:
x_N y_N


Output

Print the sum of f(T) over all non-empty subset T of S, modulo 998244353.

Examples

Input

3
-1 3
2 1
3 -2


Output

13


Input

4
1 4
2 1
3 3
4 2


Output

34


Input

10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6


Output

7222

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jealous of Mirko’s position as head of the village, Borko stormed into his tent and tried to demonstrate Mirko’s incompetence for leadership with a trick.

Borko puts three opaque cups onto the table next to each other (opening facing down) and a small ball under the leftmost cup. He then swaps two cups in one of three possible ways a number of times. Mirko has to tell which cup the ball ends up under.

Wise Mirko grins with his arms crossed while Borko struggles to move the cups faster and faster. What Borko does not know is that programmers in the back are recording all his moves and will use a simple program to determine where the ball is. Write that program.

-----Input-----
The first and only line contains a non-empty string of at most $50$ characters, Borko’s moves. Each of the characters is ‘A’, ‘B’ or ‘C’ (without quote marks).

-----Output-----
Output the index of the cup under which the ball is: $1$ if it is under the left cup, $2$ if it is under the middle cup or $3$ if it is under the right cup.

-----Examples-----
Sample Input:
AB
Sample Output:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese  and Russian. 

Chef loves brackets. So much so, that rather than just use plain brackets like (), {}, or [], he has invented his own notation that allows him to use many more types of brackets.

Each type of bracket is designated by an integer. A negative integer -x represents an opening bracket of type x; while a positive integer x represents a closing bracket of type x. Any sequence of such integers is then called a bracket-pair sequence.

A balanced bracket-pair sequence can be defined recursively as follows:

	The empty sequence is a balanced bracket-pair sequence.
	If S is a balanced bracket-pair sequence, then -x S x is a balanced bracket-pair sequence for any positive integer x.
	If S and T are balanced bracket-pair sequences, then S T is a balanced bracket-pair sequence.

For example, "-1 -2 2 -3 -4 4 3 1" is a balanced bracket-pair sequence, but "-1 -2 1 2" is not.

Chef has a bracket-pair sequence (which may or may not be balanced) consisting of N integers. There are 2^{}N ways to form a subsequence of his sequence. He wants to know how many of these subsequences are balanced.

Help him to calculate this number, modulo 10^{9}+7. 

------ Input ------ 

The first line contains a single integer N denoting the number of brackets in his sequence. 
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the types of brackets. A negative number means an opening bracket; a positive number means a closing bracket.

------ Output ------ 

In a single line print the required answer.

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

$1 ≤ N ≤ 100$
$-10^{9} ≤ A_{i} ≤ 10^{9}$$A_{i} ≠  0$
$It is not guaranteed that each opening bracket has a closing bracket of same type and vice-versa. $

------ Subtasks ------ 

$Subtask N ≤ 10 Points: 10 $
$Subtask N ≤ 20 Points: 15 $
$Subtask N ≤ 100 Points: 75 $

------ Example ------ 

Input:
11
-1 -2 9 2 -3 -4 3 4 8 8 1 

Output:
12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S consisting of 0 and 1.
Find the maximum integer K not greater than |S| such that we can turn all the characters of S into 0 by repeating the following operation some number of times.
 - Choose a contiguous segment [l,r] in S whose length is at least K (that is, r-l+1\geq K must be satisfied). For each integer i such that l\leq i\leq r, do the following: if S_i is 0, replace it with 1; if S_i is 1, replace it with 0.

-----Constraints-----
 - 1\leq |S|\leq 10^5
 - S_i(1\leq i\leq N) is either 0 or 1.

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

-----Output-----
Print the maximum integer K such that we can turn all the characters of S into 0 by repeating the operation some number of times.

-----Sample Input-----
010

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

We can turn all the characters of S into 0 by the following operations:
 - Perform the operation on the segment S[1,3] with length 3. S is now 101.
 - Perform the operation on the segment S[1,2] with length 2. S is now 011.
 - Perform the operation on the segment S[2,3] with length 2. S is now 000.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Roma (a popular Russian name that means 'Roman') loves the Little Lvov Elephant's lucky numbers.

Let us remind you that lucky numbers are positive integers whose decimal representation only contains lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Roma's got n positive integers. He wonders, how many of those integers have not more than k lucky digits? Help him, write the program that solves the problem.


-----Input-----

The first line contains two integers n, k (1 ≤ n, k ≤ 100). The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^9) — the numbers that Roma has. 

The numbers in the lines are separated by single spaces.


-----Output-----

In a single line print a single integer — the answer to the problem.


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

Output
3

Input
3 2
447 44 77

Output
2



-----Note-----

In the first sample all numbers contain at most four lucky digits, so the answer is 3.

In the second sample number 447 doesn't fit in, as it contains more than two lucky digits. All other numbers are fine, so the answer is 2.

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

N boxes are arranged systematically in a circle and numbered from 1 to N in increasing order in clockwise direction. There will be Q queries asking you whether boxes i and j can be connected by a straight rod such that this rod does not intersect ( criss - cross as seen from top view ) with any of the other rods used to join other boxes in the previous queries. If the rod does not intersect with any of the other rods, the boxes i and j will be connected by the rod , or else the connection will not be made. Every box can be connected to at most one other box. No box can be connected to itself. Infinitley many rods of all possible sizes are available.

Input:

First line comprises of two space separated integers N and Q. Then there will be Q lines, each line will consist of two space separated integers i and j.

Output:

Print the answer to each query , 'YES' if the connection can be made and 'NO' if the connection cannot be made.

Constraints:

2 ≤ N ≤ 1000

1 ≤ Q ≤ 1000

1 ≤ i,j ≤ N

SAMPLE INPUT
10 7
1 5
2 7
2 3
2 4
9 9
10 9
8 6SAMPLE OUTPUT
YES
NO
YES
NO
NO
YES
YES

Explanation

1 and 5 can be connected by a rod.
2 and 7 cannot be connected by a rod because this rod intersects with the rod connecting 1 and 5.
2 and 3 can be connected.
2 and 4 cannot be connected as 2 is already connected to 3.
9 and 9 cannot be connected as no box can be connected to itself.
10 and 9 can be connected.
8 and 6 can be connected.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two arrays A and B contains integers of size N and M, the task is to find numbers which are present in the first array, but not present in the second array.
Example 1:
Input: N = 6, M = 5
A[] = {1, 2, 3, 4, 5, 10}
B[] = {2, 3, 1, 0, 5}
Output: 4 10
Explanation: 4 and 10 are present in 
first array, but not in second array.
Example 2:
Input: N = 5, M = 5
A[] = {4, 3, 5, 9, 11}
B[] = {4, 9, 3, 11, 10}
Output: 5  
Explanation: Second array does not 
contain element 5.
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function findMissing() that takes array A, array B, integer N, and integer M  as parameters and returns an array that contains the missing elements and the order of the elements should be the same as they are in array A.
 
Expected Time Complexity: O(N+M).
Expected Auxiliary Space: O(M).
 
Constraints:
1 ≤ N, M ≤ 10^{6}
-10^{6} ≤ A[i], B[i] ≤ 10^{6}

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