vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Little boy Valera studies an algorithm of sorting an integer array. After studying the theory, he went on to the practical tasks. As a result, he wrote a program that sorts an array of n integers a_1, a_2, ..., a_{n} in the non-decreasing order. The pseudocode of the program, written by Valera, is given below. The input of the program gets number n and array a.

loop integer variable i from 1 to n - 1

    loop integer variable j from i to n - 1

        if (a_{j} > a_{j} + 1), then swap the values of elements a_{j} and a_{j} + 1



But Valera could have made a mistake, because he hasn't yet fully learned the sorting algorithm. If Valera made a mistake in his program, you need to give a counter-example that makes his program work improperly (that is, the example that makes the program sort the array not in the non-decreasing order). If such example for the given value of n doesn't exist, print -1.


-----Input-----

You've got a single integer n (1 ≤ n ≤ 50) — the size of the sorted array.


-----Output-----

Print n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100) — the counter-example, for which Valera's algorithm won't work correctly. If the counter-example that meets the described conditions is impossible to give, print -1.

If there are several counter-examples, consisting of n numbers, you are allowed to print any of them.


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

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem you will meet the simplified model of game King of Thieves.

In a new ZeptoLab game called "King of Thieves" your aim is to reach a chest with gold by controlling your character, avoiding traps and obstacles on your way. [Image] 

An interesting feature of the game is that you can design your own levels that will be available to other players. Let's consider the following simple design of a level.

A dungeon consists of n segments located at a same vertical level, each segment is either a platform that character can stand on, or a pit with a trap that makes player lose if he falls into it. All segments have the same length, platforms on the scheme of the level are represented as '*' and pits are represented as '.'. 

One of things that affects speedrun characteristics of the level is a possibility to perform a series of consecutive jumps of the same length. More formally, when the character is on the platform number i_1, he can make a sequence of jumps through the platforms i_1 < i_2 < ... < i_{k}, if i_2 - i_1 = i_3 - i_2 = ... = i_{k} - i_{k} - 1. Of course, all segments i_1, i_2, ... i_{k} should be exactly the platforms, not pits. 

Let's call a level to be good if you can perform a sequence of four jumps of the same length or in the other words there must be a sequence i_1, i_2, ..., i_5, consisting of five platforms so that the intervals between consecutive platforms are of the same length. Given the scheme of the level, check if it is good.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100) — the number of segments on the level.

Next line contains the scheme of the level represented as a string of n characters '*' and '.'.


-----Output-----

If the level is good, print the word "yes" (without the quotes), otherwise print the word "no" (without the quotes).


-----Examples-----
Input
16
.**.*..*.***.**.

Output
yes
Input
11
.*.*...*.*.

Output
no


-----Note-----

In the first sample test you may perform a sequence of jumps through platforms 2, 5, 8, 11, 14.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Phoenix loves playing with bits — specifically, by using the bitwise operations AND, OR, and XOR. He has n integers a_1, a_2, ..., a_n, and will perform q of the following queries:

  1. replace all numbers a_i where l ≤ a_i ≤ r with a_i AND x; 
  2. replace all numbers a_i where l ≤ a_i ≤ r with a_i OR x; 
  3. replace all numbers a_i where l ≤ a_i ≤ r with a_i XOR x; 
  4. output how many distinct integers a_i where l ≤ a_i ≤ r. 



For each query, Phoenix is given l, r, and x. Note that he is considering the values of the numbers, not their indices.

Input

The first line contains two integers n and q (1 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ q ≤ 10^5) — the number of integers and the number of queries, respectively.

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i < 2^{20}) — the integers that Phoenix starts with.

The next q lines contain the queries. For each query, the first integer of each line is t (1 ≤ t ≤ 4) — the type of query.

If t ∈ \{1, 2, 3\}, then three integers l_i, r_i, and x_i will follow (0 ≤ l_i, r_i, x_i < 2^{20}; l_i ≤ r_i).

Otherwise, if t=4, two integers l_i and r_i will follow (0 ≤ l_i ≤ r_i < 2^{20}).

It is guaranteed that there is at least one query where t=4.

Output

Print the answer for each query where t=4.

Examples

Input


5 6
5 4 3 2 1
1 2 3 2
4 2 5
3 2 5 3
4 1 6
2 1 1 8
4 8 10


Output


3
2
1


Input


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


Output


5
1
2

Note

In the first example: 

  * For the first query, 2 is replaced by 2 AND 2 = 2 and 3 is replaced with 3 AND 2 = 2. The set of numbers is \{1, 2, 4, 5\}.
  * For the second query, there are 3 distinct numbers between 2 and 5: 2, 4, and 5.
  * For the third query, 2 is replaced by 2 XOR 3 = 1, 4 is replaced by 4 XOR 3 = 7, and 5 is replaced by 5 XOR 3 = 6. The set of numbers is \{1, 6, 7\}.
  * For the fourth query, there are 2 distinct numbers between 1 and 6: 1 and 6.
  * For the fifth query, 1 is replaced by 1 OR 8 = 9. The set of numbers is \{6, 7, 9\}.
  * For the sixth query, there is one distinct number between 8 and 10: 9. 

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sereja is a coder and he likes to take part in Codesorfes rounds. However, Uzhland doesn't have good internet connection, so Sereja sometimes skips rounds.

Codesorfes has rounds of two types: *Div*1 (for advanced coders) and *Div*2 (for beginner coders). Two rounds, *Div*1 and *Div*2, can go simultaneously, (*Div*1 round cannot be held without *Div*2) in all other cases the rounds don't overlap in time. Each round has a unique identifier — a positive integer. The rounds are sequentially (without gaps) numbered with identifiers by the starting time of the round. The identifiers of rounds that are run simultaneously are different by one, also the identifier of the *Div*1 round is always greater.

Sereja is a beginner coder, so he can take part only in rounds of *Div*2 type. At the moment he is taking part in a *Div*2 round, its identifier equals to *x*. Sereja remembers very well that he has taken part in exactly *k* rounds before this round. Also, he remembers all identifiers of the rounds he has taken part in and all identifiers of the rounds that went simultaneously with them. Sereja doesn't remember anything about the rounds he missed.

Sereja is wondering: what minimum and what maximum number of *Div*2 rounds could he have missed? Help him find these two numbers.

Input Specification:
The first line contains two integers: *x* (1<=≤<=*x*<=≤<=4000) — the round Sereja is taking part in today, and *k* (0<=≤<=*k*<=&lt;<=4000) — the number of rounds he took part in.

Next *k* lines contain the descriptions of the rounds that Sereja took part in before. If Sereja took part in one of two simultaneous rounds, the corresponding line looks like: "1 *num*2 *num*1" (where *num*2 is the identifier of this *Div*2 round, *num*1 is the identifier of the *Div*1 round). It is guaranteed that *num*1<=-<=*num*2<==<=1. If Sereja took part in a usual *Div*2 round, then the corresponding line looks like: "2 *num*" (where *num* is the identifier of this *Div*2 round). It is guaranteed that the identifiers of all given rounds are less than *x*.

Output Specification:
Print in a single line two integers — the minimum and the maximum number of rounds that Sereja could have missed.

Demo Input:
['3 2\n2 1\n2 2\n', '9 3\n1 2 3\n2 8\n1 4 5\n', '10 0\n']

Demo Output:
['0 0', '2 3', '5 9']

Note:
In the second sample we have unused identifiers of rounds 1, 6, 7. The minimum number of rounds Sereja could have missed equals to 2. In this case, the round with the identifier 1 will be a usual *Div*2 round and the round with identifier 6 will be synchronous with the *Div*1 round. 

The maximum number of rounds equals 3. In this case all unused identifiers belong to usual *Div*2 rounds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.
The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.
Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.
Return a string of all teams sorted by the ranking system.
 
Example 1:
Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.
Team B was ranked second by 2 voters and was ranked third by 3 voters.
Team C was ranked second by 3 voters and was ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team and team B is the third.

Example 2:
Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position. 

Example 3:
Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter so his votes are used for the ranking.

Example 4:
Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
Output: "ABC"
Explanation: 
Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.
There is a tie and we rank teams ascending by their IDs.

Example 5:
Input: votes = ["M","M","M","M"]
Output: "M"
Explanation: Only team M in the competition so it has the first rank.

 
Constraints:

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length.
votes[i][j] is an English upper-case letter.
All characters of votes[i] are unique.
All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has two arrays A and B of the same size N.

In one operation, Chef can:
Choose an index i (1 ≤ i ≤ N) and swap the elements A_{i} and B_{i}.

Chef came up with a task to find the minimum possible value of (A_{max} - A_{min}) after performing the swap operation any (possibly zero) number of times. 

Since Chef is busy, can you help him solve this task?

Note that A_{max} and A_{min} denote the maximum and minimum elements of the array A respectively.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains one integer N — the number of elements in each array.
- The second line consists of N space-separated integers A_{1}, A_{2},\ldots ,A_{N} denoting the elements of the array A.
- The third line consists of N space-separated integers B_{1}, B_{2}, \ldots ,B_{N} denoting the elements of the array B.

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

For each test case, output on a new line, the minimum possible value of (A_{max} - A_{min}) in the array A after doing swap operation any number of times.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ A_{i}, B_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

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

----- Sample Output 1 ------ 
0
1
3

----- explanation 1 ------ 
Test case $1$: Chef can make the following operations:
- Operation $1$: Choose $i=1$ and swap $A_{1}$ with $B_{1}$.

By doing the above operations, array $A$ becomes $[2, 2]$. Here $(A_{max} - A_{min}) = 0$. It can be shown that this is the minimum value possible.

Test case $2$: Chef can make the following operations:
- Operation $1$: Choose $i=1$ and swap $A_{1}$ with $B_{1}$.
- Operation $2$: Choose $i=2$ and swap $A_{2}$ with $B_{2}$.

By doing the above operations, array $A$ becomes $[2, 3, 3]$. Here $(A_{max} - A_{min}) = 1$. It can be shown that this is the minimum value possible.

Test case $3$: Chef can make the following operations:
- Operation $1$: Choose $i=2$ and swap $A_{2}$ with $B_{2}$.
- Operation $2$: Choose $i=3$ and swap $A_{3}$ with $B_{3}$.

By doing the above operations, array $A$ becomes $[4, 3, 4, 1]$. Here $(A_{max} - A_{min}) = 3$. It can be shown that this is the minimum value possible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob is playing a popular game called "Dungeon". The game is played on a rectangular board consisting of W × H squares. Each square is identified with its column and row number, thus the square located in the x-th column and the y-th row is represented as (x, y). The left-most square in the top row is (0, 0) and the right-most square in the bottom row is (W-1, H-1).

Bob moves a character "BomBom" to clear the game. BomBom is initially located at (0, 0). The game is won if Bob successfully destroys all the enemy characters on the board by manipulating BomBom cleverly. The enemy characters are fixed on specific squares, and Bob can manipulate BomBom using the following two operations any number of times.

* One-square movement in the up, down, left, or right direction within the board
* Using a bomb, eliminate all the enemy characters that are located in the same column and row as that of BomBom



BomBom consumes a Cost when it moves from one square to another. BomBom can use a bomb any number of times without consuming a Cost. Use of a bomb has no effect on BomBom’s behavior and it can move even to a square where an enemy character is located.

Given the board size and enemy information, make a program to evaluate the minimum Cost BomBom consumes before it destroys all enemy characters.



Input

The input is given in the following format.


W H N
x_1 y_1
x_2 y_2
:
x_N y_N


The first line provides the number of squares in the horizontal direction W (1 ≤ W ≤ 105), in the vertical direction H (1 ≤ H ≤ 105), and the number of enemy characters N (1 ≤ N ≤ 105). Each of the subsequent N lines provides location information of the i-th enemy, column x_i (0 ≤ x_i ≤ W-1) and row y_i (0 ≤ y_i ≤ H-1). The number of enemy characters in a specific square can be either one or zero.

Output

Output the minimum Cost in a line.

Examples

Input

5 4 4
0 3
1 1
2 2
2 3


Output

2


Input

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


Output

4


Input

8 8 4
6 0
7 0
0 6
0 7


Output

0

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

Your task is to write a function which returns the sum of following series upto nth term(parameter).

    Series: 1 + 1/4 + 1/7 + 1/10 + 1/13 + 1/16 +...
 
## Rules:
 
* You need to round the answer to 2 decimal places and return it as String.

* If the given value is 0 then it should return 0.00

* You will only be given Natural Numbers as arguments.

## Examples:

    SeriesSum(1) => 1 = "1.00"
    SeriesSum(2) => 1 + 1/4 = "1.25"
    SeriesSum(5) => 1 + 1/4 + 1/7 + 1/10 + 1/13 = "1.57"
    
**NOTE**: In PHP the function is called `series_sum()`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rupsa really loves triangles. One day she came across an equilateral triangle having length of each side as an integer N. She started wondering if it was possible to transform the triangle keeping two sides fixed and alter the third side such that it still remains a triangle, but the altered side will have its length as an even integer, and the line drawn from the opposite vertex to the mid-point of the altered side is of integral length.
Since Rupsa is in a hurry to record a song for Chef as he really loves her songs, you must help her solve the problem as fast as possible.

-----Input-----
The first line of input contains an integer T denoting the number of test cases.
Each test-case contains a single integer N.

-----Output-----

For each test case, output "YES" if the triangle transformation is possible, otherwise "NO" (quotes for clarity only, do not output).

-----Constraints-----
- 1 ≤ T ≤ 106
- 1 ≤ N ≤ 5 x 106

-----Sub tasks-----
- Subtask #1: 1 ≤ T ≤ 100, 1 ≤ N ≤ 104 (10 points)
- Subtask #2: 1 ≤ T ≤ 104, 1 ≤ N ≤ 106 (30 points)
- Subtask #3: Original Constraints (60 points)

-----Example-----
Input:2
5
3

Output:YES
NO

-----Explanation-----
- In test case 1, make the length of any one side 6, and it will suffice.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arild just turned $1$ year old, and is currently learning how to count. His favorite thing to count is how many mouthfuls he has in a meal: every time he gets a bite, he will count it by saying the number out loud. 

Unfortunately, talking while having a mouthful sometimes causes Arild to mumble incomprehensibly, making it hard to know how far he has counted. Sometimes you even suspect he loses his count! You decide to write a program to determine whether Arild’s counting makes sense or not.

-----Input-----
The first line of input contains an integer $n$ ($1 \le n \le 1000$), the number of bites Arild receives. Then second line contains $n$ space-separated words spoken by Arild, the $i$’th of which is either a non-negative integer $a_ i$ ($0 \le a_ i \le 10000$) or the string “mumble”.

-----Output-----
If Arild’s counting might make sense, print the string “makes sense”. Otherwise, print the string “something is fishy”.

-----Examples-----
Sample Input 1:
5
1 2 3 mumble 5
Sample Output 1:
makes sense

Sample Input 2:
8
1 2 3 mumble mumble 7 mumble 8
Sample Output 2:
something is fishy

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 |s| small english letters.

In one move you can replace any character of this string to the next character in alphabetical order (a will be replaced with b, s will be replaced with t, etc.). You cannot replace letter z with any other letter.

Your target is to make some number of moves (not necessary minimal) to get string abcdefghijklmnopqrstuvwxyz (english alphabet) as a subsequence. Subsequence of the string is the string that is obtained by deleting characters at some positions. You need to print the string that will be obtained from the given string and will be contain english alphabet as a subsequence or say that it is impossible.

Input

The only one line of the input consisting of the string s consisting of |s| (1 ≤ |s| ≤ 105) small english letters.

Output

If you can get a string that can be obtained from the given string and will contain english alphabet as a subsequence, print it. Otherwise print «-1» (without quotes).

Examples

Input

aacceeggiikkmmooqqssuuwwyy


Output

abcdefghijklmnopqrstuvwxyz


Input

thereisnoanswer


Output

-1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The preferred way to generate user login in Polygon is to concatenate a prefix of the user's first name and a prefix of their last name, in that order. Each prefix must be non-empty, and any of the prefixes can be the full name. Typically there are multiple possible logins for each person.

You are given the first and the last name of a user. Return the alphabetically earliest login they can get (regardless of other potential Polygon users).

As a reminder, a prefix of a string *s* is its substring which occurs at the beginning of *s*: "a", "ab", "abc" etc. are prefixes of string "{abcdef}" but "b" and 'bc" are not. A string *a* is alphabetically earlier than a string *b*, if *a* is a prefix of *b*, or *a* and *b* coincide up to some position, and then *a* has a letter that is alphabetically earlier than the corresponding letter in *b*: "a" and "ab" are alphabetically earlier than "ac" but "b" and "ba" are alphabetically later than "ac".

Input Specification:
The input consists of a single line containing two space-separated strings: the first and the last names. Each character of each string is a lowercase English letter. The length of each string is between 1 and 10, inclusive.

Output Specification:
Output a single string — alphabetically earliest possible login formed from these names. The output should be given in lowercase as well.

Demo Input:
['harry potter\n', 'tom riddle\n']

Demo Output:
['hap\n', 'tomr\n']

Note:
none

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

Time Limit: 3 seconds

Memory Limit: 256 megabytes

Problem Description:
You are given a convex polygon. Count, please, the number of triangles that contain a given point in the plane and their vertices are the vertices of the polygon. It is guaranteed, that the point doesn't lie on the sides and the diagonals of the polygon.

Input Specification:
The first line contains integer *n* — the number of vertices of the polygon (3<=≤<=*n*<=≤<=100000). The polygon description is following: *n* lines containing coordinates of the vertices in clockwise order (integer *x* and *y* not greater than 109 by absolute value). It is guaranteed that the given polygon is nondegenerate and convex (no three points lie on the same line).

The next line contains integer *t* (1<=≤<=*t*<=≤<=20) — the number of points which you should count the answer for. It is followed by *t* lines with coordinates of the points (integer *x* and *y* not greater than 109 by absolute value).

Output Specification:
The output should contain *t* integer numbers, each on a separate line, where *i*-th number is the answer for the *i*-th point.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Demo Input:
['4\n5 0\n0 0\n0 5\n5 5\n1\n1 3\n', '3\n0 0\n0 5\n5 0\n2\n1 1\n10 10\n', '5\n7 6\n6 3\n4 1\n1 2\n2 4\n4\n3 3\n2 3\n5 5\n4 2\n']

Demo Output:
['2\n', '1\n0\n', '5\n3\n3\n4\n']

Note:
none

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