vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Recently Polycarpus has learned the "bitwise AND" operation (which is also called "AND") of non-negative integers. Now he wants to demonstrate the school IT teacher his superb manipulation with the learned operation.

For that Polycarpus came to school a little earlier and wrote on the board a sequence of non-negative integers a_1, a_2, ..., a_{n}. He also wrote a square matrix b of size n × n. The element of matrix b that sits in the i-th row in the j-th column (we'll denote it as b_{ij}) equals:  the "bitwise AND" of numbers a_{i} and a_{j} (that is, b_{ij} = a_{i} & a_{j}), if i ≠ j;  -1, if i = j. 

Having written out matrix b, Polycarpus got very happy and wiped a off the blackboard. But the thing is, the teacher will want this sequence to check whether Polycarpus' calculations were correct. Polycarus urgently needs to restore the removed sequence of integers, or else he won't prove that he can count correctly.

Help Polycarpus, given matrix b, restore the sequence of numbers a_1, a_2, ..., a_{n}, that he has removed from the board. Polycarpus doesn't like large numbers, so any number in the restored sequence mustn't exceed 10^9.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100) — the size of square matrix b. Next n lines contain matrix b. The i-th of these lines contains n space-separated integers: the j-th number represents the element of matrix b_{ij}. It is guaranteed, that for all i (1 ≤ i ≤ n) the following condition fulfills: b_{ii} = -1. It is guaranteed that for all i, j (1 ≤ i, j ≤ n; i ≠ j) the following condition fulfills: 0 ≤ b_{ij} ≤ 10^9, b_{ij} = b_{ji}.


-----Output-----

Print n non-negative integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9) — the sequence that Polycarpus wiped off the board. Separate the numbers by whitespaces. 

It is guaranteed that there is sequence a that satisfies the problem conditions. If there are multiple such sequences, you are allowed to print any of them.


-----Examples-----
Input
1
-1

Output
0 
Input
3
-1 18 0
18 -1 0
0 0 -1

Output
18 18 0 
Input
4
-1 128 128 128
128 -1 148 160
128 148 -1 128
128 160 128 -1

Output
128 180 148 160 


-----Note-----

If you do not know what is the "bitwise AND" operation please read: http://en.wikipedia.org/wiki/Bitwise_operation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a consisting of n integers, and q queries to it. i-th query is denoted by two integers l_i and r_i. For each query, you have to find any integer that occurs exactly once in the subarray of a from index l_i to index r_i (a subarray is a contiguous subsegment of an array). For example, if a = [1, 1, 2, 3, 2, 4], then for query (l_i = 2, r_i = 6) the subarray we are interested in is [1, 2, 3, 2, 4], and possible answers are 1, 3 and 4; for query (l_i = 1, r_i = 2) the subarray we are interested in is [1, 1], and there is no such element that occurs exactly once.

Can you answer all of the queries?

Input

The first line contains one integer n (1 ≤ n ≤ 5 ⋅ 10^5).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 5 ⋅ 10^5).

The third line contains one integer q (1 ≤ q ≤ 5 ⋅ 10^5).

Then q lines follow, i-th line containing two integers l_i and r_i representing i-th query (1 ≤ l_i ≤ r_i ≤ n).

Output

Answer the queries as follows:

If there is no integer such that it occurs in the subarray from index l_i to index r_i exactly once, print 0. Otherwise print any such integer.

Example

Input

6
1 1 2 3 2 4
2
2 6
1 2


Output

4
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima worked all day and wrote down on a long paper strip his favorite number $n$ consisting of $l$ digits. Unfortunately, the strip turned out to be so long that it didn't fit in the Dima's bookshelf.

To solve the issue, Dima decided to split the strip into two non-empty parts so that each of them contains a positive integer without leading zeros. After that he will compute the sum of the two integers and write it down on a new strip.

Dima wants the resulting integer to be as small as possible, because it increases the chances that the sum will fit it in the bookshelf. Help Dima decide what is the minimum sum he can obtain.


-----Input-----

The first line contains a single integer $l$ ($2 \le l \le 100\,000$) — the length of the Dima's favorite number.

The second line contains the positive integer $n$ initially written on the strip: the Dima's favorite number.

The integer $n$ consists of exactly $l$ digits and it does not contain leading zeros. Dima guarantees, that there is at least one valid way to split the strip.


-----Output-----

Print a single integer — the smallest number Dima can obtain.


-----Examples-----
Input
7
1234567

Output
1801

Input
3
101

Output
11



-----Note-----

In the first example Dima can split the number $1234567$ into integers $1234$ and $567$. Their sum is $1801$.

In the second example Dima can split the number $101$ into integers $10$ and $1$. Their sum is $11$. Note that it is impossible to split the strip into "1" and "01" since the numbers can't start with zeros.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has a pile, that consists of some number of stones. $n$ times he either took one stone from the pile or added one stone to the pile. The pile was non-empty before each operation of taking one stone from the pile.

You are given $n$ operations which Vasya has made. Find the minimal possible number of stones that can be in the pile after making these operations.


-----Input-----

The first line contains one positive integer $n$ — the number of operations, that have been made by Vasya ($1 \leq n \leq 100$).

The next line contains the string $s$, consisting of $n$ symbols, equal to "-" (without quotes) or "+" (without quotes). If Vasya took the stone on $i$-th operation, $s_i$ is equal to "-" (without quotes), if added, $s_i$ is equal to "+" (without quotes).


-----Output-----

Print one integer — the minimal possible number of stones that can be in the pile after these $n$ operations.


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

Output
0
Input
4
++++

Output
4
Input
2
-+

Output
1
Input
5
++-++

Output
3


-----Note-----

In the first test, if Vasya had $3$ stones in the pile at the beginning, after making operations the number of stones will be equal to $0$. It is impossible to have less number of piles, so the answer is $0$. Please notice, that the number of stones at the beginning can't be less, than $3$, because in this case, Vasya won't be able to take a stone on some operation (the pile will be empty).

In the second test, if Vasya had $0$ stones in the pile at the beginning, after making operations the number of stones will be equal to $4$. It is impossible to have less number of piles because after making $4$ operations the number of stones in the pile increases on $4$ stones. So, the answer is $4$.

In the third test, if Vasya had $1$ stone in the pile at the beginning, after making operations the number of stones will be equal to $1$. It can be proved, that it is impossible to have less number of stones after making the operations.

In the fourth test, if Vasya had $0$ stones in the pile at the beginning, after making operations the number of stones will be equal to $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given integer K and a string S of length N, we denote power of S, as the length of a longest substring occurring in S at least K times.

Given K and S, find the power of S.

Constraints:

1 ≤ N ≤ 10^6
1 ≤ K ≤ N
S consists of latin lowercase letters only

Input format:

In the first line there are two integers K and N separated by a single space. The second line constains string S itself.

Output format:

In one line, output the power of string S for a given K.

SAMPLE INPUT
2 11
abrakadabra

SAMPLE OUTPUT
4

Explanation

Substring "abra" occurs in S two times and it is the longest substring of all substrings of S occurring at least two times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 
Chef likes problems related to numbers a lot. He is generally quite good at solving these kinds of problems, but today he got stuck at one number theory problem, and so he asks your help to solve it.

Given a positive integer N, find out how many positive integers X satisfy the equation X + S(X) + S(S(X)) = N, where S(X) denoting sum of digits of X in decimal (base 10) representation.

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

The only line of the input contains one integer number - N.

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

Output single integer in a line denoting the count of number of positive integers X satisfying the above given equation.

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

$1 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
6
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 
Example 1. Only one positive integer X = 2 satisfies the equation X + S(X) + S(S(X)) = 6, as X + S(X) + S(S(X)) = 2 + 2 + 2 = 6.

----- Sample Input 2 ------ 
9939
----- Sample Output 2 ------ 
4
----- explanation 2 ------ 
Example 2.X can be 9898, 9907, 9910 and 9913. 
9898 + S(9898) + S(S(9898)) = 9898 + 34 + 7 = 9939
9907 + S(9907) + S(S(9907)) = 9907 + 25 + 7 = 9939
9910 + S(9910) + S(S(9910)) = 9910 + 19 + 10 = 9939
9913 + S(9913) + S(S(9913)) = 9913 + 22 + 4 = 9939
You can verify that there is not other positive value of X satisfying the given equation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Polycarp noticed that some of the buttons of his keyboard are malfunctioning. For simplicity, we assume that Polycarp's keyboard contains $26$ buttons (one for each letter of the Latin alphabet). Each button is either working fine or malfunctioning. 

To check which buttons need replacement, Polycarp pressed some buttons in sequence, and a string $s$ appeared on the screen. When Polycarp presses a button with character $c$, one of the following events happened:

  if the button was working correctly, a character $c$ appeared at the end of the string Polycarp was typing;  if the button was malfunctioning, two characters $c$ appeared at the end of the string. 

For example, suppose the buttons corresponding to characters a and c are working correctly, and the button corresponding to b is malfunctioning. If Polycarp presses the buttons in the order a, b, a, c, a, b, a, then the string he is typing changes as follows: a $\rightarrow$ abb $\rightarrow$ abba $\rightarrow$ abbac $\rightarrow$ abbaca $\rightarrow$ abbacabb $\rightarrow$ abbacabba.

You are given a string $s$ which appeared on the screen after Polycarp pressed some buttons. Help Polycarp to determine which buttons are working correctly for sure (that is, this string could not appear on the screen if any of these buttons was malfunctioning).

You may assume that the buttons don't start malfunctioning when Polycarp types the string: each button either works correctly throughout the whole process, or malfunctions throughout the whole process.


-----Input-----

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

Then the test cases follow. Each test case is represented by one line containing a string $s$ consisting of no less than $1$ and no more than $500$ lowercase Latin letters.


-----Output-----

For each test case, print one line containing a string $res$. The string $res$ should contain all characters which correspond to buttons that work correctly in alphabetical order, without any separators or repetitions. If all buttons may malfunction, $res$ should be empty.


-----Example-----
Input
4
a
zzaaz
ccff
cbddbb

Output
a
z

bc

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Akshay is interested in mathematics, one day he came across a problem of modulus operator.He has  a list of M integers say arr[M] and has to find all integers K such that :
- K > 1
- arr[1]%K = arr[2]%K = arr[3]%K = … = arr[M]%K where '%' is a modulus operator.
Help Akshay to find all such K's.

-----Input:-----
- First line of input contains an integer M. Then M lines follow each containing one integer of the list. Input data is such that at least one integer K will always exist.

-----Output:-----
- Output all possible integers K separated by space in increasing order.

-----Constraints-----
- 2<= M <=100
- 1< value of each integer <109
- All integers will be distinct

-----Sample Input:-----
3
38
6
34

-----Sample Output:-----
2 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
100 years have passed since the last victory of the man versus computer in Go. Technologies made a huge step forward and robots conquered the Earth! It's time for the final fight between human and robot that will decide the faith of the planet.

The following game was chosen for the fights: initially there is a polynomial P(x) = a_{n}x^{n} + a_{n} - 1x^{n} - 1 + ... + a_1x + a_0,  with yet undefined coefficients and the integer k. Players alternate their turns. At each turn, a player pick some index j, such that coefficient a_{j} that stay near x^{j} is not determined yet and sets it to any value (integer or real, positive or negative, 0 is also allowed). Computer moves first. The human will be declared the winner if and only if the resulting polynomial will be divisible by Q(x) = x - k.

Polynomial P(x) is said to be divisible by polynomial Q(x) if there exists a representation P(x) = B(x)Q(x), where B(x) is also some polynomial.

Some moves have been made already and now you wonder, is it true that human can guarantee the victory if he plays optimally?


-----Input-----

The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, |k| ≤ 10 000) — the size of the polynomial and the integer k.

The i-th of the following n + 1 lines contain character '?' if the coefficient near x^{i} - 1 is yet undefined or the integer value a_{i}, if the coefficient is already known ( - 10 000 ≤ a_{i} ≤ 10 000). Each of integers a_{i} (and even a_{n}) may be equal to 0.

Please note, that it's not guaranteed that you are given the position of the game where it's computer's turn to move.


-----Output-----

Print "Yes" (without quotes) if the human has winning strategy, or "No" (without quotes) otherwise.


-----Examples-----
Input
1 2
-1
?

Output
Yes

Input
2 100
-10000
0
1

Output
Yes
Input
4 5
?
1
?
1
?

Output
No


-----Note-----

In the first sample, computer set a_0 to  - 1 on the first move, so if human can set coefficient a_1 to 0.5 and win.

In the second sample, all coefficients are already set and the resulting polynomial is divisible by x - 100, so the human has won.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
To save money, Santa Claus has started hiring other animals besides reindeer to pull his sleigh via short term ‘gig’ contracts. As a result, the actual animals that show up to pull his sleigh for any given trip can vary greatly in size.

Last week he had $2$ buffalo, $37$ voles and a schnauzer. Unfortunately, both buffalo were hitched on the left side and the entire sleigh flipped over in mid-flight due to the weight imbalance.

To prevent such accidents in the future, Santa needs to divide the animals for a given trip into two groups such that the sum of the weights of all animals in one group equals the sum of the weights of all animals in the other. To make the hitching process efficient, Santa is seeking an integer target weight $t$ such that all animals that are lighter than $t$ go in one group and those heavier than $t$ go into the other. If there are multiple such $t$, he wants the smallest one. There’s one small wrinkle: what should be done if there some animals have weight exactly equal to $t$? Santa solves the problem this way: if there are an even number of such animals, he divides them equally among the two groups (thus distributing the weight evenly). But if there are an odd number of such animals, then one of those animals is sent to work with the elves to make toys (it is not put in either group), and the remaining (now an even number) are divided evenly among the two groups.

-----Input-----
Input describes a list of animals’ weights. The first line contains an integer $m$ ($2 \le m \le 10^5$), indicating the number of animals. The next $m$ lines each have a positive integer. These are the weights of the animals (in ounces). Animals weighing more than $20000$ ounces are too big to pull the sleigh so no given weight exceeds this maximum.

-----Output-----
Output the smallest integer target weight $t$, as described above. It’s guaranteed that it is possible to find such an integer.

-----Examples-----
Sample Input 1:
4
3
6
1
2
Sample Output 1:
4

Sample Input 2:
4
11
8
3
10
Sample Output 2:
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
you are given an array of size N. You need to select K elements from the array such that the difference between the max number among selected and the min number among selected array elements should be minimum. Print the minimum difference.

INPUT:
First line N number i.e., length of array
Second line K number 
Next N lines contains a number for each line

OUTPUT:
Print the minimum possible difference

0<N<10^5
0<K<N
0<number<10^9

SAMPLE INPUT
5
3
1
2
3
4
5

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polly, the programming parrot, has escaped. As Johan is in desperate need for some programming skill, he wants to find her. The only clue that Johan has about the escape route is that Polly flew into his kitchen.

Johan has $N$ boxes on his kitchen table, and each box has a certain probability to contain the parrot. Each box also requires a certain amount of energy in order to be opened. Checking all the boxes would for sure find the disobedient parrot, but there is a problem. Johan is a very lazy person, and he wants to spend as little energy as possible while trying to find Polly. Aware of his own laziness, Johan decided that he will be satisfied with finding the parrot with at least probability $P$, as long as he minimizes the energy wasted in opening boxes. Can you help him?

-----Input-----
Input starts with a line with an integer $1 \leq N \leq 10^3$, the number of boxes in Johan’s kitchen and a floating point number $0 \leq P \leq 1$, the minimum probability with which Johan wants to find Polly. Then $N$ lines follow: each line containing an integer $0 \leq e_ i \leq 10^3$ describing the amount of energy needed to open box $i$, and a floating point number $0 \leq p_ i \leq 1$ describing the probability that Polly is inside box number $i$. All probabilities are given with at most four digits after the decimal point.

-----Output-----
Output should contain a single integer on a single line: the minimum amount of energy Johan has to waste while finding Polly with at least probability $P$.

-----Examples-----
Sample Input 1:
2 0.5
2 0.5
1 0.5
Sample Output 1:
1

Sample Input 2:
2 0.5
2 0.51
1 0.49
Sample Output 2:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasily the bear has a favorite rectangle, it has one vertex at point (0, 0), and the opposite vertex at point (x, y). Of course, the sides of Vasya's favorite rectangle are parallel to the coordinate axes. 

Vasya also loves triangles, if the triangles have one vertex at point B = (0, 0). That's why today he asks you to find two points A = (x_1, y_1) and C = (x_2, y_2), such that the following conditions hold:  the coordinates of points: x_1, x_2, y_1, y_2 are integers. Besides, the following inequation holds: x_1 < x_2;  the triangle formed by point A, B and C is rectangular and isosceles ($\angle A B C$ is right);  all points of the favorite rectangle are located inside or on the border of triangle ABC;  the area of triangle ABC is as small as possible. 

Help the bear, find the required points. It is not so hard to proof that these points are unique.


-----Input-----

The first line contains two integers x, y ( - 10^9 ≤ x, y ≤ 10^9, x ≠ 0, y ≠ 0).


-----Output-----

Print in the single line four integers x_1, y_1, x_2, y_2 — the coordinates of the required points.


-----Examples-----
Input
10 5

Output
0 15 15 0

Input
-10 5

Output
-15 0 0 15



-----Note-----

[Image]

Figure to the first sample

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N cards. A number a_i is written on the i-th card.

Alice and Bob will play a game using these cards. In this game, Alice and Bob alternately take one card. Alice goes first.

The game ends when all the cards are taken by the two players, and the score of each player is the sum of the numbers written on the cards he/she has taken. When both players take the optimal strategy to maximize their scores, find Alice's score minus Bob's score.

-----Constraints-----
 - N is an integer between 1 and 100 (inclusive).
 - a_i \ (1 \leq i \leq N) is an integer between 1 and 100 (inclusive).

-----Input-----
Input is given from Standard Input in the following format:  
N
a_1 a_2 a_3 ... a_N

-----Output-----
Print Alice's score minus Bob's score when both players take the optimal strategy to maximize their scores.

-----Sample Input-----
2
3 1

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

First, Alice will take the card with 3. Then, Bob will take the card with 1.
The difference of their scores will be 3 - 1 = 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a sequence 2,5,16,65,........Given an integer n as input. You have to find the value at the nth position in the sequence.
 
Example 1:
Input: n = 4
Output: 65
Example 2:
Input: n = 10
Output: 9864101
 
Your Task:
You don't need to read or print anything, Your task is to complete the function NthTerm() which takes n as input parameter and returns value at nth position of the given sequence modulo 10^{9} + 7.
 
Expected Time Complexity:  O(n)
Expected Space Complexity: O(1)
 
Constraints:
1 <= n <= 10^{4}

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