vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a 0-indexed array S with N strings, numbered 0 through N-1, and Q queries to handle.
All strings in this problem are nonempty and consist of lowercase English letters.

Let's create an integer variable LAST_YES to decipher the input.
LAST_YES should be equal to the index of the last query that was of the first type and had an answer "YES".
Queries are 0-indexed.
LAST_YES is initially equal to zero.
Note that LAST_YES can't be changed in the first query because the first query's index is zero.

There are two types of queries.

The first type is of ciphered form "1 t", where t is a string of lowercase English characters.
Add LAST_YES to each character in t to get its deciphered value.
E.g. the given string cdxyyz with LAST_YES equal to 2 denotes a deciphered string efzaab.
You should check whether at least one element of S is a substring of deciphered t.
In a single line print "YES" or "NO".

The second type is of ciphered form "2 i alpha", where i and alpha are integers.
i (0 ≤ i < |S|) denotes an index in the array S.
alpha (0 ≤ alpha < 26) denotes a single lowercase English letter.
To decipher a query you should add LAST_YES to i and to alpha.
In the other words, you can get a deciphered values using the following C++ and Java code:
i = (i + LAST_YES) % N;
alpha = (alpha + LAST_YES) % 26;
After deciphering a query you should add a letter alpha at the end of the i-th string in S.

Input format
The first line contains two integers N and Q, denoting the size of the array S and the number of queries, respectively.

The next N lines describe the array S, one string per line.
All strings are nonempty and consist of lowercase English letters.

The next Q lines contain queries.
Each query is of form "1 t" or "2 i alpha".

For the first type of query, t is a nonempty string of lowercase English letters.

For the second type, i and alpha are integers, and 0 ≤ i < |S|, 0 ≤ alpha < 26.

Output format
For each query of the first type print the answer "YES" or "NO" (without the quotes) in a separate line.

Constraints
1 ≤ N, Q ≤ 200,000
The sum of the initial lengths of strings in S won't exceed 200,000.
The sum of the lengths of strings t in queries won't exceed 200,000.

SAMPLE INPUT
5 7
aba
broadway
test
why
i
1 tst
1 text
2 1 2
1 caaabaaac
1 qbpqfkd
2 4 0
1 wdwdsdubaa

SAMPLE OUTPUT
NO
NO
YES
YES
NO

Explanation

The answer is "NO" for the queries #0 and #1.

In the query #2 a string broadway extends to broadwayc.

In the query #3 the answer is YES because the first string (aba) in S is a substring of caaabaaac.
LAST_YES is equal to 3 now.

The query #4 asks about deciphered string testing for which the last string in S is a substring (i as a substring of testing).
LAST_YES is 4 now.

The query #5 ask to add a letter "e" (because 0+LAST_YES = 4) at the end of a string of index (4+LAST_YES)%N = 8%N = 3.
So, we change why to whye.

In the last query a string t is equal to ahahwhyfee after the deciphering.
It doesn't have substrings in S, so the answer is NO.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand. Help Vasya find the maximal number of such integers.

For instance, if we are given an array $[10, 20, 30, 40]$, we can permute it so that it becomes $[20, 40, 10, 30]$. Then on the first and the second positions the integers became larger ($20>10$, $40>20$) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals $2$. Read the note for the first example, there is one more demonstrative test case.

Help Vasya to permute integers in such way that the number of positions in a new array, where integers are greater than in the original one, is maximal.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array.


-----Output-----

Print a single integer — the maximal number of the array's elements which after a permutation will stand on the position where a smaller element stood in the initial array.


-----Examples-----
Input
7
10 1 1 1 5 5 3

Output
4

Input
5
1 1 1 1 1

Output
0



-----Note-----

In the first sample, one of the best permutations is $[1, 5, 5, 3, 10, 1, 1]$. On the positions from second to fifth the elements became larger, so the answer for this permutation is 4.

In the second sample, there is no way to increase any element with a permutation, so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Chess For Three

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alex, Bob and Carl will soon participate in a team chess tournament. Since they are all in the same team, they have decided to practise really hard before the tournament. But it's a bit difficult for them because chess is a game for two players, not three.

So they play with each other according to following rules:
 -  Alex and Bob play the first game, and Carl is spectating; -  When the game ends, the one who lost the game becomes the spectator in the next game, and the one who was spectating plays against the winner. 
Alex, Bob and Carl play in such a way that there are no draws.

Today they have played *n* games, and for each of these games they remember who was the winner. They decided to make up a log of games describing who won each game. But now they doubt if the information in the log is correct, and they want to know if the situation described in the log they made up was possible (that is, no game is won by someone who is spectating if Alex, Bob and Carl play according to the rules). Help them to check it!

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=100) — the number of games Alex, Bob and Carl played.

Then *n* lines follow, describing the game log. *i*-th line contains one integer *a**i* (1<=≤<=*a**i*<=≤<=3) which is equal to 1 if Alex won *i*-th game, to 2 if Bob won *i*-th game and 3 if Carl won *i*-th game.

Output Specification:
Print YES if the situation described in the log was possible. Otherwise print NO.

Demo Input:
['3\n1\n1\n2\n', '2\n1\n2\n']

Demo Output:
['YES\n', 'NO\n']

Note:
In the first example the possible situation is:
 1.  Alex wins, Carl starts playing instead of Bob; 1.  Alex wins, Bob replaces Carl; 1.  Bob wins. 
The situation in the second example is impossible because Bob loses the first game, so he cannot win the second one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Ms Swan bought an orange in a shop. The orange consisted of n·k segments, numbered with integers from 1 to n·k. 

There were k children waiting for Ms Swan at home. The children have recently learned about the orange and they decided to divide it between them. For that each child took a piece of paper and wrote the number of the segment that he would like to get: the i-th (1 ≤ i ≤ k) child wrote the number ai (1 ≤ ai ≤ n·k). All numbers ai accidentally turned out to be different.

Now the children wonder, how to divide the orange so as to meet these conditions:

  * each child gets exactly n orange segments; 
  * the i-th child gets the segment with number ai for sure; 
  * no segment goes to two children simultaneously. 



Help the children, divide the orange and fulfill the requirements, described above.

Input

The first line contains two integers n, k (1 ≤ n, k ≤ 30). The second line contains k space-separated integers a1, a2, ..., ak (1 ≤ ai ≤ n·k), where ai is the number of the orange segment that the i-th child would like to get.

It is guaranteed that all numbers ai are distinct.

Output

Print exactly n·k distinct integers. The first n integers represent the indexes of the segments the first child will get, the second n integers represent the indexes of the segments the second child will get, and so on. Separate the printed numbers with whitespaces.

You can print a child's segment indexes in any order. It is guaranteed that the answer always exists. If there are multiple correct answers, print any of them.

Examples

Input

2 2
4 1


Output

2 4 
1 3 


Input

3 1
2


Output

3 2 1 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call an array a of size n coprime iff gcd(a1, a2, ..., an) = 1, where gcd is the greatest common divisor of the arguments.

You are given two numbers n and k. For each i (1 ≤ i ≤ k) you have to determine the number of coprime arrays a of size n such that for every j (1 ≤ j ≤ n) 1 ≤ aj ≤ i. Since the answers can be very large, you have to calculate them modulo 109 + 7.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 2·106) — the size of the desired arrays and the maximum upper bound on elements, respectively.

Output

Since printing 2·106 numbers may take a lot of time, you have to output the answer in such a way:

Let bi be the number of coprime arrays with elements in range [1, i], taken modulo 109 + 7. You have to print <image>, taken modulo 109 + 7. Here <image> denotes bitwise xor operation (^ in C++ or Java, xor in Pascal).

Examples

Input

3 4


Output

82


Input

2000000 8


Output

339310063

Note

Explanation of the example:

Since the number of coprime arrays is large, we will list the arrays that are non-coprime, but contain only elements in range [1, i]:

For i = 1, the only array is coprime. b1 = 1.

For i = 2, array [2, 2, 2] is not coprime. b2 = 7.

For i = 3, arrays [2, 2, 2] and [3, 3, 3] are not coprime. b3 = 25.

For i = 4, arrays [2, 2, 2], [3, 3, 3], [2, 2, 4], [2, 4, 2], [2, 4, 4], [4, 2, 2], [4, 2, 4], [4, 4, 2] and [4, 4, 4] are not coprime. b4 = 55.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. The company decides to build warehouses to ensure that for any town X, there will be a warehouse located either in X or in an immediately neighboring town of X.

Write a program to find the minimum number of warehouses the company has to build.

[Input]:
Input will be given in the following format 
N M
S1 E1 (Start Pt and End Pt of a direct route)
S2 E2
S3 E3
....
SM EM
Each route is bidirectional
No combination of towns will be repeated.  

[Output]:
Output should be in a file in the following format
Wx - Minimum # of warehouses

*Problem provided by JDA

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

SAMPLE OUTPUT
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem is the most boring one you've ever seen. 

Given a sequence of integers a_1, a_2, ..., a_{n} and a non-negative integer h, our goal is to partition the sequence into two subsequences (not necessarily consist of continuous elements). Each element of the original sequence should be contained in exactly one of the result subsequences. Note, that one of the result subsequences can be empty.

Let's define function f(a_{i}, a_{j}) on pairs of distinct elements (that is i ≠ j) in the original sequence. If a_{i} and a_{j} are in the same subsequence in the current partition then f(a_{i}, a_{j}) = a_{i} + a_{j} otherwise f(a_{i}, a_{j}) = a_{i} + a_{j} + h. 

Consider all possible values of the function f for some partition. We'll call the goodness of this partiotion the difference between the maximum value of function f and the minimum value of function f.

Your task is to find a partition of the given sequence a that have the minimal possible goodness among all possible partitions.


-----Input-----

The first line of input contains integers n and h (2 ≤ n ≤ 10^5, 0 ≤ h ≤ 10^8). In the second line there is a list of n space-separated integers representing a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^8).


-----Output-----

The first line of output should contain the required minimum goodness. 

The second line describes the optimal partition. You should print n whitespace-separated integers in the second line. The i-th integer is 1 if a_{i} is in the first subsequence otherwise it should be 2.

If there are several possible correct answers you are allowed to print any of them.


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

Output
1
1 2 2 

Input
5 10
0 1 0 2 1

Output
3
2 2 2 2 2 



-----Note-----

In the first sample the values of f are as follows: f(1, 2) = 1 + 2 + 2 = 5, f(1, 3) = 1 + 3 + 2 = 6 and f(2, 3) = 2 + 3 = 5. So the difference between maximum and minimum values of f is 1.

In the second sample the value of h is large, so it's better for one of the sub-sequences to be empty.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note the unusual memory limit for this problem.

You are given an undirected graph consisting of n vertices and m edges. The vertices are numbered with integers from 1 to n, the edges are numbered with integers from 1 to m. Each edge can be unpainted or be painted in one of the k colors, which are numbered with integers from 1 to k. Initially, none of the edges is painted in any of the colors.

You get queries of the form "Repaint edge ei to color ci". At any time the graph formed by the edges of the same color must be bipartite. If after the repaint this condition is violated, then the query is considered to be invalid and edge ei keeps its color. Otherwise, edge ei is repainted in color ci, and the query is considered to valid.

Recall that the graph is called bipartite if the set of its vertices can be divided into two parts so that no edge connected vertices of the same parts.

For example, suppose you are given a triangle graph, that is a graph with three vertices and edges (1, 2), (2, 3) and (3, 1). Suppose that the first two edges are painted color 1, and the third one is painted color 2. Then the query of "repaint the third edge in color 1" will be incorrect because after its execution the graph formed by the edges of color 1 will not be bipartite. On the other hand, it is possible to repaint the second edge in color 2.

You receive q queries. For each query, you should either apply it, and report that the query is valid, or report that the query is invalid.

Input

The first line contains integers n, m, k, q (2 ≤ n ≤ 5·105, 1 ≤ m, q ≤ 5·105, 1 ≤ k ≤ 50) — the number of vertices, the number of edges, the number of colors and the number of queries. 

Then follow m edges of the graph in the form ai, bi (1 ≤ ai, bi ≤ n). 

Then follow q queries of the form ei, ci (1 ≤ ei ≤ m, 1 ≤ ci ≤ k).

It is guaranteed that the graph doesn't contain multiple edges and loops.

Output

For each query print "YES" (without the quotes), if it is valid, or "NO" (without the quotes), if this query destroys the bipartivity of the graph formed by the edges of some color.

Examples

Input

3 3 2 5
1 2
2 3
1 3
1 1
2 1
3 2
3 1
2 2


Output

YES
YES
YES
NO
YES

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A girl named Xenia has a cupboard that looks like an arc from ahead. The arc is made of a semicircle with radius *r* (the cupboard's top) and two walls of height *h* (the cupboard's sides). The cupboard's depth is *r*, that is, it looks like a rectangle with base *r* and height *h*<=+<=*r* from the sides. The figure below shows what the cupboard looks like (the front view is on the left, the side view is on the right).

Xenia got lots of balloons for her birthday. The girl hates the mess, so she wants to store the balloons in the cupboard. Luckily, each balloon is a sphere with radius . Help Xenia calculate the maximum number of balloons she can put in her cupboard. 

You can say that a balloon is in the cupboard if you can't see any part of the balloon on the left or right view. The balloons in the cupboard can touch each other. It is not allowed to squeeze the balloons or deform them in any way. You can assume that the cupboard's walls are negligibly thin.

Input Specification:
The single line contains two integers *r*,<=*h* (1<=≤<=*r*,<=*h*<=≤<=107).

Output Specification:
Print a single integer — the maximum number of balloons Xenia can put in the cupboard.

Demo Input:
['1 1\n', '1 2\n', '2 1\n']

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

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You come home and fell some unpleasant smell. Where is it coming from?

You are given an array *a*. You have to answer the following queries: 
 1.  You are given two integers *l* and *r*. Let *c**i* be the number of occurrences of *i* in *a**l*:<=*r*, where *a**l*:<=*r* is the subarray of *a* from *l*-th element to *r*-th inclusive. Find the Mex of {*c*0,<=*c*1,<=...,<=*c*109} 1.  You are given two integers *p* to *x*. Change *a**p* to *x*. 
The Mex of a multiset of numbers is the smallest non-negative integer not in the set.

Note that in this problem all elements of *a* are positive, which means that *c*0 = 0 and 0 is never the answer for the query of the second type.

Input Specification:
The first line of input contains two integers *n* and *q* (1<=≤<=*n*,<=*q*<=≤<=100<=000) — the length of the array and the number of queries respectively.

The second line of input contains *n* integers — *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=109).

Each of the next *q* lines describes a single query.

The first type of query is described by three integers *t**i*<==<=1, *l**i*, *r**i*, where 1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n* — the bounds of the subarray.

The second type of query is described by three integers *t**i*<==<=2, *p**i*, *x**i*, where 1<=≤<=*p**i*<=≤<=*n* is the index of the element, which must be changed and 1<=≤<=*x**i*<=≤<=109 is the new value.

Output Specification:
For each query of the first type output a single integer  — the Mex of {*c*0,<=*c*1,<=...,<=*c*109}.

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

Demo Output:
['2\n3\n2\n']

Note:
The subarray of the first query consists of the single element — 1. 

The subarray of the second query consists of four 2s, one 3 and two 1s.

The subarray of the fourth query consists of three 1s, three 2s and one 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers, where all elements but one occur twice, find the unique element.  

Example 

$a=[1,2,3,4,3,2,1]$  

The unique element is $\begin{array}{c}4\end{array}$.  

Function Description  

Complete the lonelyinteger function in the editor below.   

lonelyinteger has the following parameter(s):  

int a[n]: an array of integers   

Returns  

int: the element that occurs only once  

Input Format

The first line contains a single integer, $n$, the number of integers in the array. 

The second line contains $n$ space-separated integers that describe the values in $\boldsymbol{a}$.

Constraints

$1\leq n<100$  
It is guaranteed that $n$ is an odd number and that there is one unique element.  
$0\leq a[i]\leq100$, where $0\leq i<n$.

Sample Input 0
1
1

Sample Output 0
1

Explanation 0

There is only one element in the array, thus it is unique.

Sample Input 1
3
1 1 2

Sample Output 1
2

Explanation 1

We have two $\mbox{1}$'s, and $2$ is unique. 

Sample Input 2
5
0 0 1 2 1

Sample Output 2
2

Explanation 2

We have two $\mbox{0}$'s, two $\mbox{1}$'s, and one $2$.  $2$ is unique.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Divyank is in love with arrays.So while solving problems on arrays Divyank encountered the following problem :-

F(A) for an array A of size N is defined as sum of absolute difference between the consecutive numbers of the array.
e.g. for array A having elements as 3 5 1 F(A) will be (5-3)+(5-1) = 6.

Now you're given an array A and you have to distribute all the elements of this array into two empty arrays B and C in such a way that numbers in these arrays are in the same order as they were in array A.

e.g. if A is 1, 2, 3, 4, 5, 6 then one of the possible ways of distributing elements of A among B and C is as follows :-

B =  1, 2, 4, 5

C =  3, 6

Now you have to make the distribution in such a way that F(B)+F(C) is minimum.

Input :

First line of the input contains an integer T,number of test cases to follow.

First line of each test case is the total number of elements in the array A

Second line of each test case contains all the elements of the array as N space separated integers.

Output :

For each test case calculate the minimum value of F(B)+F(C).

Constraints :

1 ≤ T ≤ 15

1 ≤ N ≤ 2000

All elements in the array are between 1 and 10^6 both inclusive.

SAMPLE INPUT
1
5
2 5 7 8 9

SAMPLE OUTPUT
4

Explanation

There are many ways to distribute array A among B and C

Possibility 1

B : 2 8

C : 5 7 9

Here, F(B) + F(C) is 10

Possibility 2

B : 2

C : 5 7 8 9

Here, F(B) + F(C) is 4.

There are many other possibilities but the best one for the required task is as described in the Possibility 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The final match of the Berland Football Cup has been held recently. The referee has shown $n$ yellow cards throughout the match. At the beginning of the match there were $a_1$ players in the first team and $a_2$ players in the second team.

The rules of sending players off the game are a bit different in Berland football. If a player from the first team receives $k_1$ yellow cards throughout the match, he can no longer participate in the match — he's sent off. And if a player from the second team receives $k_2$ yellow cards, he's sent off. After a player leaves the match, he can no longer receive any yellow cards. Each of $n$ yellow cards was shown to exactly one player. Even if all players from one team (or even from both teams) leave the match, the game still continues.

The referee has lost his records on who has received each yellow card. Help him to determine the minimum and the maximum number of players that could have been thrown out of the game.


-----Input-----

The first line contains one integer $a_1$ $(1 \le a_1 \le 1\,000)$ — the number of players in the first team.

The second line contains one integer $a_2$ $(1 \le a_2 \le 1\,000)$ — the number of players in the second team.

The third line contains one integer $k_1$ $(1 \le k_1 \le 1\,000)$ — the maximum number of yellow cards a player from the first team can receive (after receiving that many yellow cards, he leaves the game).

The fourth line contains one integer $k_2$ $(1 \le k_2 \le 1\,000)$ — the maximum number of yellow cards a player from the second team can receive (after receiving that many yellow cards, he leaves the game).

The fifth line contains one integer $n$ $(1 \le n \le a_1 \cdot k_1 + a_2 \cdot k_2)$ — the number of yellow cards that have been shown during the match.


-----Output-----

Print two integers — the minimum and the maximum number of players that could have been thrown out of the game.


-----Examples-----
Input
2
3
5
1
8

Output
0 4

Input
3
1
6
7
25

Output
4 4

Input
6
4
9
10
89

Output
5 9



-----Note-----

In the first example it could be possible that no player left the game, so the first number in the output is $0$. The maximum possible number of players that could have been forced to leave the game is $4$ — one player from the first team, and three players from the second.

In the second example the maximum possible number of yellow cards has been shown $(3 \cdot 6 + 1 \cdot 7 = 25)$, so in any case all players were sent off.

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