vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Consider a football tournament where n teams participate. Each team has two football kits: for home games, and for away games. The kit for home games of the i-th team has color x_{i} and the kit for away games of this team has color y_{i} (x_{i} ≠ y_{i}).

In the tournament, each team plays exactly one home game and exactly one away game with each other team (n(n - 1) games in total). The team, that plays the home game, traditionally plays in its home kit. The team that plays an away game plays in its away kit. However, if two teams has the kits of the same color, they cannot be distinguished. In this case the away team plays in its home kit.

Calculate how many games in the described tournament each team plays in its home kit and how many games it plays in its away kit.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^5) — the number of teams. Next n lines contain the description of the teams. The i-th line contains two space-separated numbers x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ 10^5; x_{i} ≠ y_{i}) — the color numbers for the home and away kits of the i-th team.


-----Output-----

For each team, print on a single line two space-separated integers — the number of games this team is going to play in home and away kits, correspondingly. Print the answers for the teams in the order they appeared in the input.


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

Output
2 0
2 0

Input
3
1 2
2 1
1 3

Output
3 1
4 0
2 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
CodeMart is a shopping platform and it is distributing gift vouchers to its esteemed users. The voucher can be redeemed by providing a fixed amount of shopping credits to the platform. One credit is sent by a user to the platform by doing one occurance in CodeMart. Since there is a huge rush of people you are required to manage the users on the basis of first come first serve. The user which came first and has exactly k occurrences at last is given the voucher first. You are given an array arr[ ] with the id's of N users in chronological order of their occurances . You are required to print the id of the user which will be given the voucher first. If no such user meets the condition print "-1".
Example 1:
Input:
N = 7 
K = 2
arr[] = {1, 7, 4, 3, 4, 8, 7} 
Output: 7
Explanation: Both 7 and 4 occur 2 times.
But 7 is the first that occurs 2 times.  
Example 2:
Input:
N = 6 
K = 1 
arr[] = {4, 1, 6, 1, 6, 4} 
Output: -1 
Explanation: No one occurs exactly 1 time.
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 firstElement() that takes array arr, integer n and integer k as input parameters and returns the required answer.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(max(arr[i])).
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ arr[i] ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Ant on the Tree

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Connected undirected graph without cycles is called a tree. Trees is a class of graphs which is interesting not only for people, but for ants too.

An ant stands at the root of some tree. He sees that there are *n* vertexes in the tree, and they are connected by *n*<=-<=1 edges so that there is a path between any pair of vertexes. A leaf is a distinct from root vertex, which is connected with exactly one other vertex.

The ant wants to visit every vertex in the tree and return to the root, passing every edge twice. In addition, he wants to visit the leaves in a specific order. You are to find some possible route of the ant.

Input Specification:
The first line contains integer *n* (3<=≤<=*n*<=≤<=300) — amount of vertexes in the tree. Next *n*<=-<=1 lines describe edges. Each edge is described with two integers — indexes of vertexes which it connects. Each edge can be passed in any direction. Vertexes are numbered starting from 1. The root of the tree has number 1. The last line contains *k* integers, where *k* is amount of leaves in the tree. These numbers describe the order in which the leaves should be visited. It is guaranteed that each leaf appears in this order exactly once.

Output Specification:
If the required route doesn't exist, output -1. Otherwise, output 2*n*<=-<=1 numbers, describing the route. Every time the ant comes to a vertex, output it's index.

Demo Input:
['3\n1 2\n2 3\n3\n', '6\n1 2\n1 3\n2 4\n4 5\n4 6\n5 6 3\n', '6\n1 2\n1 3\n2 4\n4 5\n4 6\n5 3 6\n']

Demo Output:
['1 2 3 2 1 ', '1 2 4 5 4 6 4 2 1 3 1 ', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Emuskald is addicted to Codeforces, and keeps refreshing the main page not to miss any changes in the "recent actions" list. He likes to read thread conversations where each thread consists of multiple messages.

Recent actions shows a list of n different threads ordered by the time of the latest message in the thread. When a new message is posted in a thread that thread jumps on the top of the list. No two messages of different threads are ever posted at the same time.

Emuskald has just finished reading all his opened threads and refreshes the main page for some more messages to feed his addiction. He notices that no new threads have appeared in the list and at the i-th place in the list there is a thread that was at the a_{i}-th place before the refresh. He doesn't want to waste any time reading old messages so he wants to open only threads with new messages.

Help Emuskald find out the number of threads that surely have new messages. A thread x surely has a new message if there is no such sequence of thread updates (posting messages) that both conditions hold:   thread x is not updated (it has no new messages);  the list order 1, 2, ..., n changes to a_1, a_2, ..., a_{n}. 


-----Input-----

The first line of input contains an integer n, the number of threads (1 ≤ n ≤ 10^5). The next line contains a list of n space-separated integers a_1, a_2, ..., a_{n} where a_{i} (1 ≤ a_{i} ≤ n) is the old position of the i-th thread in the new list. It is guaranteed that all of the a_{i} are distinct.


-----Output-----

Output a single integer — the number of threads that surely contain a new message.


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

Output
2

Input
3
1 2 3

Output
0

Input
4
4 3 2 1

Output
3



-----Note-----

In the first test case, threads 2 and 5 are placed before the thread 1, so these threads must contain new messages. Threads 1, 3 and 4 may contain no new messages, if only threads 2 and 5 have new messages.

In the second test case, there may be no new messages at all, since the thread order hasn't changed.

In the third test case, only thread 1 can contain no new messages.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Game of Robots

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In late autumn evening *n* robots gathered in the cheerful company of friends. Each robot has a unique identifier — an integer from 1 to 109.

At some moment, robots decided to play the game "Snowball". Below there are the rules of this game. First, all robots stand in a row. Then the first robot says his identifier. After that the second robot says the identifier of the first robot and then says his own identifier. Then the third robot says the identifier of the first robot, then says the identifier of the second robot and after that says his own. This process continues from left to right until the *n*-th robot says his identifier.

Your task is to determine the *k*-th identifier to be pronounced.

Input Specification:
The first line contains two positive integers *n* and *k* (1<=≤<=*n*<=≤<=100<=000, 1<=≤<=*k*<=≤<=*min*(2·109,<=*n*·(*n*<=+<=1)<=/<=2).

The second line contains the sequence *id*1,<=*id*2,<=...,<=*id**n* (1<=≤<=*id**i*<=≤<=109) — identifiers of roborts. It is guaranteed that all identifiers are different.

Output Specification:
Print the *k*-th pronounced identifier (assume that the numeration starts from 1).

Demo Input:
['2 2\n1 2\n', '4 5\n10 4 18 3\n']

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

Note:
In the first sample identifiers of robots will be pronounced in the following order: 1, 1, 2. As *k* = 2, the answer equals to 1.

In the second test case identifiers of robots will be pronounced in the following order: 10, 10, 4, 10, 4, 18, 10, 4, 18, 3. As *k* = 5, the answer equals to 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya walks late at night along a straight street of length l, lit by n lanterns. Consider the coordinate system with the beginning of the street corresponding to the point 0, and its end corresponding to the point l. Then the i-th lantern is at the point a_{i}. The lantern lights all points of the street that are at the distance of at most d from it, where d is some positive number, common for all lanterns. 

Vanya wonders: what is the minimum light radius d should the lanterns have to light the whole street?


-----Input-----

The first line contains two integers n, l (1 ≤ n ≤ 1000, 1 ≤ l ≤ 10^9) — the number of lanterns and the length of the street respectively. 

The next line contains n integers a_{i} (0 ≤ a_{i} ≤ l). Multiple lanterns can be located at the same point. The lanterns may be located at the ends of the street.


-----Output-----

Print the minimum light radius d, needed to light the whole street. The answer will be considered correct if its absolute or relative error doesn't exceed 10^{ - 9}.


-----Examples-----
Input
7 15
15 5 3 7 9 14 0

Output
2.5000000000

Input
2 5
2 5

Output
2.0000000000



-----Note-----

Consider the second sample. At d = 2 the first lantern will light the segment [0, 4] of the street, and the second lantern will light segment [3, 5]. Thus, the whole street will be lit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has to solve exactly $n$ problems to improve his programming skill before an important programming competition. But this competition will be held very soon, most precisely, it will start in $k$ days. It means that Polycarp has exactly $k$ days for training!

Polycarp doesn't want to procrastinate, so he wants to solve at least one problem during each of $k$ days. He also doesn't want to overwork, so if he solves $x$ problems during some day, he should solve no more than $2x$ problems during the next day. And, at last, he wants to improve his skill, so if he solves $x$ problems during some day, he should solve at least $x+1$ problem during the next day.

More formally: let $[a_1, a_2, \dots, a_k]$ be the array of numbers of problems solved by Polycarp. The $i$-th element of this array is the number of problems Polycarp solves during the $i$-th day of his training. Then the following conditions must be satisfied:   sum of all $a_i$ for $i$ from $1$ to $k$ should be $n$;  $a_i$ should be greater than zero for each $i$ from $1$ to $k$;  the condition $a_i < a_{i + 1} \le 2 a_i$ should be satisfied for each $i$ from $1$ to $k-1$. 

Your problem is to find any array $a$ of length $k$ satisfying the conditions above or say that it is impossible to do it.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 10^9, 1 \le k \le 10^5$) — the number of problems Polycarp wants to solve and the number of days Polycarp wants to train.


-----Output-----

If it is impossible to find any array $a$ of length $k$ satisfying Polycarp's rules of training, print "NO" in the first line.

Otherwise print "YES" in the first line, then print $k$ integers $a_1, a_2, \dots, a_k$ in the second line, where $a_i$ should be the number of problems Polycarp should solve during the $i$-th day. If there are multiple answers, you can print any.


-----Examples-----
Input
26 6

Output
YES
1 2 4 5 6 8 

Input
8 3

Output
NO

Input
1 1

Output
YES
1 

Input
9 4

Output
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you might know, the memory in current computers consists of a sequence of bits and each of these bits can be in two possible states. Megan’s company has now developed a great new memory unit where every bit has three possible states. This would all be great, if it wasn’t for Megan’s boss. The boss wants her to write a program for this memory unit for integer operations, but instead of using ternary base (i.e., base 3), Megan’s boss decided that the bits should be interpreted as a binary number, with the exception that the digit 2 is allowed as well. 

For example, $201$ in this strange representation is $2\cdot 2^2+0\cdot 2^1+ 1\cdot 2^0=9$. Some numbers are shorter in this representation, but for other numbers it doesn’t help at all – for instance, $15$ is $1111$ in binary and this is the only way of writing it in the new representation as well.

It seems that there is nothing else that Megan can do to convince her boss. Since she likes math, she started wondering about different representations of the same number. For example 9 has three representations: $201, 121$ and $1001$. Can you help her figure out how many representations a given number has?

-----Input-----
The first and only line of the input contains a string consisting of ’0’ and ’1’. The string represents a non-negative integer $N$ in binary. The leftmost bit is the most significant one. The number of bits will be at least $1$ and at most $10000$.

-----Output-----
Output a line giving the number of different binary representations of $N$ that also use $2$ as a digit. Since this number might be big, output the remainder modulo $1000000009$.

-----Examples-----
Sample Input 1:
1001
Sample Output 1:
3

Sample Input 2:
1111
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the infinite sequence of integers: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5.... The sequence is built in the following way: at first the number 1 is written out, then the numbers from 1 to 2, then the numbers from 1 to 3, then the numbers from 1 to 4 and so on. Note that the sequence contains numbers, not digits. For example number 10 first appears in the sequence in position 55 (the elements are numerated from one).

Find the number on the n-th position of the sequence.


-----Input-----

The only line contains integer n (1 ≤ n ≤ 10^14) — the position of the number to find.

Note that the given number is too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


-----Output-----

Print the element in the n-th position of the sequence (the elements are numerated from one).


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

Output
2

Input
5

Output
2

Input
10

Output
4

Input
55

Output
10

Input
56

Output
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A few years ago, Hitagi encountered a giant crab, who stole the whole of her body weight. Ever since, she tried to avoid contact with others, for fear that this secret might be noticed.

To get rid of the oddity and recover her weight, a special integer sequence is needed. Hitagi's sequence has been broken for a long time, but now Kaiki provides an opportunity.

Hitagi's sequence a has a length of n. Lost elements in it are denoted by zeros. Kaiki provides another sequence b, whose length k equals the number of lost elements in a (i.e. the number of zeros). Hitagi is to replace each zero in a with an element from b so that each element in b should be used exactly once. Hitagi knows, however, that, apart from 0, no integer occurs in a and b more than once in total.

If the resulting sequence is not an increasing sequence, then it has the power to recover Hitagi from the oddity. You are to determine whether this is possible, or Kaiki's sequence is just another fake. In other words, you should detect whether it is possible to replace each zero in a with an integer from b so that each integer from b is used exactly once, and the resulting sequence is not increasing.

Input

The first line of input contains two space-separated positive integers n (2 ≤ n ≤ 100) and k (1 ≤ k ≤ n) — the lengths of sequence a and b respectively.

The second line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 200) — Hitagi's broken sequence with exactly k zero elements.

The third line contains k space-separated integers b1, b2, ..., bk (1 ≤ bi ≤ 200) — the elements to fill into Hitagi's sequence.

Input guarantees that apart from 0, no integer occurs in a and b more than once in total.

Output

Output "Yes" if it's possible to replace zeros in a with elements in b and make the resulting sequence not increasing, and "No" otherwise.

Examples

Input

4 2
11 0 0 14
5 4


Output

Yes


Input

6 1
2 3 0 8 9 10
5


Output

No


Input

4 1
8 94 0 4
89


Output

Yes


Input

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


Output

Yes

Note

In the first sample: 

  * Sequence a is 11, 0, 0, 14. 
  * Two of the elements are lost, and the candidates in b are 5 and 4. 
  * There are two possible resulting sequences: 11, 5, 4, 14 and 11, 4, 5, 14, both of which fulfill the requirements. Thus the answer is "Yes". 



In the second sample, the only possible resulting sequence is 2, 3, 5, 8, 9, 10, which is an increasing sequence and therefore invalid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ashish has an array $a$ of size $n$.

A subsequence of $a$ is defined as a sequence that can be obtained from $a$ by deleting some elements (possibly none), without changing the order of the remaining elements.

Consider a subsequence $s$ of $a$. He defines the cost of $s$ as the minimum between:   The maximum among all elements at odd indices of $s$.  The maximum among all elements at even indices of $s$. 

Note that the index of an element is its index in $s$, rather than its index in $a$. The positions are numbered from $1$. So, the cost of $s$ is equal to $min(max(s_1, s_3, s_5, \ldots), max(s_2, s_4, s_6, \ldots))$.

For example, the cost of $\{7, 5, 6\}$ is $min( max(7, 6), max(5) ) = min(7, 5) = 5$.

Help him find the minimum cost of a subsequence of size $k$.


-----Input-----

The first line contains two integers $n$ and $k$ ($2 \leq k \leq n \leq 2 \cdot 10^5$)  — the size of the array $a$ and the size of the subsequence.

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


-----Output-----

Output a single integer  — the minimum cost of a subsequence of size $k$.


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

Output
1
Input
4 3
1 2 3 4

Output
2
Input
5 3
5 3 4 2 6

Output
2
Input
6 4
5 3 50 2 4 5

Output
3


-----Note-----

In the first test, consider the subsequence $s$ = $\{1, 3\}$. Here the cost is equal to $min(max(1), max(3)) = 1$.

In the second test, consider the subsequence $s$ = $\{1, 2, 4\}$. Here the cost is equal to $min(max(1, 4), max(2)) = 2$.

In the fourth test, consider the subsequence $s$ = $\{3, 50, 2, 4\}$. Here the cost is equal to $min(max(3, 2), max(50, 4)) = 3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sunuke came up with a pun called "s de t t", but forgot it. Sunuke remembers the following.

* The length of s is N.
* The length of t is M.
* t is a substring of s. (There is a part of consecutive M characters of s that matches t.)



Divide the number of possible combinations as (s, t) by 1,000,000,007 to find the remainder. However, it is assumed that there are A types of characters.

Constraints

* 1 ≤ N ≤ 200
* 1 ≤ M ≤ 50
* M ≤ N
* 1 ≤ A ≤ 1000

Input


N M A


Output

Divide the number of character string pairs (s, t) that satisfy the condition by 1,000,000,007 and output the remainder.

Examples

Input

3 2 2


Output

14


Input

200 50 1000


Output

678200960

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a collection of rocks, each rock has a positive integer weight.
Each turn, we choose any two rocks and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)
 
Example 1:
Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We can combine 2 and 4 to get 2 so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1 so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0 so the array converts to [1] then that's the optimal value.

 
Note:

1 <= stones.length <= 30
1 <= stones[i] <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oleg the bank client solves an interesting chess problem: place on n × n chessboard the maximum number of rooks so that they don't beat each other. Of course, no two rooks can share the same cell.

Remind that a rook standing in the cell (a, b) beats a rook standing in the cell (x, y) if and only if a = x or b = y.

Unfortunately (of fortunately?) for Oleg the answer in this problem was always n, so the task bored Oleg soon. He decided to make it more difficult by removing some cells from the board. If a cell is deleted, Oleg can't put a rook there, but rooks do beat each other "through" deleted cells.

Oleg deletes the cells in groups, namely, he repeatedly choose a rectangle with sides parallel to the board sides and deletes all the cells inside the rectangle. Formally, if he chooses a rectangle, lower left cell of which has coordinates (x1, y1), and upper right cell of which has coordinates (x2, y2), then he deletes all such cells with coordinates (x, y) that x1 ≤ x ≤ x2 and y1 ≤ y ≤ y2. It is guaranteed that no cell is deleted twice, i.e. the chosen rectangles do not intersect.

This version of the problem Oleg can't solve, and his friend Igor is busy at a conference, so he can't help Oleg.

You are the last hope for Oleg! Help him: given the size of the board and the deleted rectangles find the maximum possible number of rooks that could be placed on the board so that no two rooks beat each other.

Input

The first line contains single integer n (1 ≤ n ≤ 10000) — the size of the board.

The second line contains single integer q (0 ≤ q ≤ 10000) — the number of deleted rectangles.

The next q lines contain the information about the deleted rectangles.

Each of these lines contains four integers x1, y1, x2 and y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n) — the coordinates of the lower left and the upper right cells of a deleted rectangle.

If is guaranteed that the rectangles do not intersect.

Output

In the only line print the maximum number of rooks Oleg can place on the board so that no two rooks beat each other.

Examples

Input

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


Output

3


Input

8
4
2 2 4 6
1 8 1 8
7 1 8 2
5 4 6 8


Output

8

Note

Here is the board and the example of rooks placement in the first example:

<image>

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