vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Akira, the student council president of A High School, decided to investigate which club activities the A High School students belong to. A High School has N students numbered 1 to N and M types of club activities numbered 1 to M. There is no limit to the number of people in each club activity, and there can be 0 club activities. However, according to the school rules of A High School, students can only belong to one club activity. All students follow this school rule.

Akira asked student members to investigate and obtained records for line K, such as each line being one of the following:

* Student a and student b belong to the same club activities.
* Student c belongs to club activity x.



However, there may be a contradiction in this record that would cause someone to violate school rules. Akira decided to look at the first line in order and look for the first line that could be judged to be inconsistent.

Create a program that finds the number of the first line that can be determined to be inconsistent given a record of K lines.



Input

The input is given in the following format.


NMK
record1
record2
::
recordK


The first line gives the number of students N (1 ≤ N ≤ 100000), the number of club activity types M (1 ≤ M ≤ 100000), and the number of recorded lines K (1 ≤ K ≤ 200000). Each line of record, recordi, is given in the following K lines in one of the following formats:


1 a b


Or


2 c x


When the first digit is "1", it indicates that student a (1 ≤ a ≤ N) and student b (1 ≤ b ≤ N) belong to the same club activity. However, a ≠ b.

When the first digit is "2", it indicates that student c (1 ≤ c ≤ N) belongs to club activity x (1 ≤ x ≤ M).

Output

Output the number of the first line that can be determined to be inconsistent on one line. If not found, output 0 on one line.

Examples

Input

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


Output

4


Input

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


Output

0


Input

3 2 2
1 1 2
2 1 1


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer n, find the smallest positive integer root of equation x, or else print -1 if no roots are found.
Equation: x^2+s(x)*x-n=0
where x, n are positive integers, s(x) is the function, equal to the sum of digits of number x in the decimal number system.
 
Example 1:
Input: n = 110
Output: 10
Explanation: x=10 is the minimum root. 
As s(10)=1+0=1 and 102+1*10-110=0.
Example 2:
Input: n = 5
Output: -1
Explanation: There is no x possible which
satisfy the above equation.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function Root() which takes n as input parameter and retuns the minimum root of the given equation. If not possible returns -1.
 
Expected Time Complexity: O(k) where k is constant
Expected Space Complexity: O(1)
 
Constraints:
1 <= n <= 10^{18}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: GukiZ hates Boxes

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Professor GukiZ is concerned about making his way to school, because massive piles of boxes are blocking his way. 

In total there are *n* piles of boxes, arranged in a line, from left to right, *i*-th pile (1<=≤<=*i*<=≤<=*n*) containing *a**i* boxes. Luckily, *m* students are willing to help GukiZ by removing all the boxes from his way. Students are working simultaneously. At time 0, all students are located left of the first pile. It takes one second for every student to move from this position to the first pile, and after that, every student must start performing sequence of two possible operations, each taking one second to complete. Possible operations are:
1.  If *i*<=≠<=*n*, move from pile *i* to pile *i*<=+<=1;1.  If pile located at the position of student is not empty, remove one box from it.
GukiZ's students aren't smart at all, so they need you to tell them how to remove boxes before professor comes (he is very impatient man, and doesn't want to wait). They ask you to calculate minumum time *t* in seconds for which they can remove all the boxes from GukiZ's way. Note that students can be positioned in any manner after *t* seconds, but all the boxes must be removed.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=105), the number of piles of boxes and the number of GukiZ's students. 

The second line contains *n* integers *a*1,<=*a*2,<=... *a**n* (0<=≤<=*a**i*<=≤<=109) where *a**i* represents the number of boxes on *i*-th pile. It's guaranteed that at least one pile of is non-empty.

Output Specification:
In a single line, print one number, minimum time needed to remove all the boxes in seconds.

Demo Input:
['2 1\n1 1\n', '3 2\n1 0 2\n', '4 100\n3 4 5 4\n']

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

Note:
First sample: Student will first move to the first pile (1 second), then remove box from first pile (1 second), then move to the second pile (1 second) and finally remove the box from second pile (1 second).

Second sample: One of optimal solutions is to send one student to remove a box from the first pile and a box from the third pile, and send another student to remove a box from the third pile. Overall, 5 seconds.

Third sample: With a lot of available students, send three of them to remove boxes from the first pile, four of them to remove boxes from the second pile, five of them to remove boxes from the third pile, and four of them to remove boxes from the fourth pile. Process will be over in 5 seconds, when removing the boxes from the last pile is finished.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yet another education system reform has been carried out in Berland recently. The innovations are as follows:

An academic year now consists of n days. Each day pupils study exactly one of m subjects, besides, each subject is studied for no more than one day. After the lessons of the i-th subject pupils get the home task that contains no less than ai and no more than bi exercises. Besides, each subject has a special attribute, the complexity (ci). A school can make its own timetable, considering the following conditions are satisfied:

  * the timetable should contain the subjects in the order of the complexity's strict increasing; 
  * each day, except for the first one, the task should contain either k times more exercises, or more by k compared to the previous day (more formally: let's call the number of home task exercises in the i-th day as xi, then for each i (1 < i ≤ n): either xi = k + xi - 1 or xi = k·xi - 1 must be true); 
  * the total number of exercises in all home tasks should be maximal possible. 



All limitations are separately set for each school.

It turned out that in many cases ai and bi reach 1016 (however, as the Berland Minister of Education is famous for his love to half-measures, the value of bi - ai doesn't exceed 100). That also happened in the Berland School №256. Nevertheless, you as the school's principal still have to work out the timetable for the next academic year...

Input

The first line contains three integers n, m, k (1 ≤ n ≤ m ≤ 50, 1 ≤ k ≤ 100) which represent the number of days in an academic year, the number of subjects and the k parameter correspondingly. Each of the following m lines contains the description of a subject as three integers ai, bi, ci (1 ≤ ai ≤ bi ≤ 1016, bi - ai ≤ 100, 1 ≤ ci ≤ 100) — two limitations to the number of exercises on the i-th subject and the complexity of the i-th subject, correspondingly. Distinct subjects can have the same complexity. The subjects are numbered with integers from 1 to m. 

Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use the cin stream or the %I64d specificator.

Output

If no valid solution exists, print the single word "NO" (without the quotes). Otherwise, the first line should contain the word "YES" (without the quotes) and the next n lines should contain any timetable that satisfies all the conditions. The i + 1-th line should contain two positive integers: the number of the subject to study on the i-th day and the number of home task exercises given for this subject. The timetable should contain exactly n subjects.

Examples

Input

4 5 2
1 10 1
1 10 2
1 10 3
1 20 4
1 100 5


Output

YES
2 8
3 10
4 20
5 40


Input

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


Output

NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary tree, find its level order traversal.
Level order traversal of a tree is breadth-first traversal for the tree.
Example 1:
Input:
    1
  /   \ 
 3     2
Output:1 3 2
Example 2:
Input:
        10
     /      \
    20       30
  /   \
 40   60
Output:10 20 30 40 60
Your Task:
You don't have to take any input. Complete the function levelOrder() that takes the root node as input parameter and returns a list of integers containing the level order traversal of the given Binary Tree.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ Number of nodes ≤ 105
1 ≤ Data of a node ≤ 105

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three integers $x, y$ and $n$. Your task is to find the maximum integer $k$ such that $0 \le k \le n$ that $k \bmod x = y$, where $\bmod$ is modulo operation. Many programming languages use percent operator % to implement it.

In other words, with given $x, y$ and $n$ you need to find the maximum possible integer from $0$ to $n$ that has the remainder $y$ modulo $x$.

You have to answer $t$ independent test cases. It is guaranteed that such $k$ exists for each test case.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 5 \cdot 10^4$) — the number of test cases. The next $t$ lines contain test cases.

The only line of the test case contains three integers $x, y$ and $n$ ($2 \le x \le 10^9;~ 0 \le y < x;~ y \le n \le 10^9$).

It can be shown that such $k$ always exists under the given constraints.


-----Output-----

For each test case, print the answer — maximum non-negative integer $k$ such that $0 \le k \le n$ and $k \bmod x = y$. It is guaranteed that the answer always exists.


-----Example-----
Input
7
7 5 12345
5 0 4
10 5 15
17 8 54321
499999993 9 1000000000
10 5 187
2 0 999999999

Output
12339
0
15
54306
999999995
185
999999998



-----Note-----

In the first test case of the example, the answer is $12339 = 7 \cdot 1762 + 5$ (thus, $12339 \bmod 7 = 5$). It is obvious that there is no greater integer not exceeding $12345$ which has the remainder $5$ modulo $7$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a sequence $a$ with length $N$ created by removing some elements (possibly zero) from a permutation of numbers $(1, 2, \dots, N)$. When an element is removed, the length of the sequence doesn't change, but there is an empty spot left where the removed element was. You also have an integer $K$.
Let's call a permutation $p_1, p_2, \dots, p_N$ good if:
- it is possible replace empty spots in $a$ by numbers in such a way that we obtain the permutation $p$
- the number of positions $i$ ($1 < i \le N$) such that $p_i > p_{i-1}$ is equal to $K$
Your task is to find the number of good permutations.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $a_1, a_2, \dots, a_N$. Each element of this sequence is either $0$ (indicating an empty spot previously occupied by a removed element) or an integer between $1$ and $N$ inclusive.

-----Output-----
For each test case, print a single line containing one integer — the number of good permutations.

-----Constraints-----
- $1 \le T \le 300$
- $0 \le K < N \le 8$
- each integer between $1$ and $N$ inclusive appears in $a$ at most once

-----Example Input-----
1
3 1
2 0 0

-----Example Output-----
2

-----Explanation-----
Example case 1: The two possible good permutations are $(2,3,1)$ and $(2,1,3)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After conquering Britannia, the great Roman general Agricola decided all of his new cities should take advantage of the natural springs found aplenty. He appointed his advisor Wessus Waterus to try to find a way to get each town a fresh supply of water.

There are many springs and many towns and between each are the natural hills and valleys of Roman Britain. Wessus doesn’t want to waste the Imperial coin. He has been tasked with linking each town to a spring by a series of aqueducts using as little material as possible. Water, as we know, only flows downhill so any aqueduct must go from a higher point to a lower; intervening hills, springs and towns are no problem since they can be tunnelled through and on. The only requirement is that all aqueduct components start and end on hilltops.

Any spring must only serve one town, but the Romans are clever enough to find a way for aqueducts to pass each other. Roman engineering is excellent, but has its limits: aqueducts can only be of a limited length.

-----Input-----
 - One line containing four integers: $n,s,t$ and $q$ where $0 < n \le 500$ is the number of hills, $1 \le s \le 40$ is the number of springs, $1 \le t \le s$ is the number of towns and $q$ ($1 \le q \le 3\cdot 10^6$) is the maximum aqueduct length.
 - $N$ more lines, each giving the space-separated integers $x_ i, y_ i, h_ i$: the coordinates and height of a hill ($0 \le |x|, |y|, h \le 10^6$). These hills are numbered $1$ to $n$ in the order given.
 - One line containing $s$ space-separated integers $i_ j$ ($1 \le i_ j \le n$), each representing the number of a hill on which a spring can be found.
 - One line containing $t$ space-separated integers $i_ j$ ($1 \le i_ j \le n$), each giving the number of a hill on which the town can be found.

Each hill may only have at most one spring or one town.

-----Output-----
Output one line with one real number, denoting the minimum total length of all aqueducts needed to supply each town with fresh water from its own unique spring or IMPOSSIBLE if there is no way to achieve this. Your answer should be correct up to an absolute or relative precision of $10^{-6}$.

-----Examples-----
Sample Input:
6 2 2 8
0 0 6
3 4 7
0 8 8
6 8 8
6 0 6
6 4 8
3 4
1 5
Sample Output:
20.396078

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The ultimate battle has begun in Tekken.  
Each fight has two players. Let the initial health of the players be X and Y, then, after the fight, the health of both the players reduces by \texttt{min(X, Y)}.

Anna, Bob, and Claudio have initial health levels of A, B, and C respectively. Each pair of players fight exactly once.  
Considering that you can schedule the fight between each pair in any order, find whether Anna can have a positive health level at the end of the battle.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains three space-separated integers A, B,  and C — the initial health levels of Anna, Bob, and Claudio respectively.

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

For each test case, output on a new line, YES, if you can schedule the fight between each pair in an order such that Anna can have a positive health at the end of the battle. Otherwise, output NO.

You can print each character in uppercase or lowercase. For example NO, no, No, and nO are all considered identical.

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

$1 ≤ T ≤ 1000$
$0 ≤ A, B, C ≤ 1000$

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

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
Test case $1$: Consider the following sequence of fights:
- Fight $1$: Anna and Bob fight. Thus, the health level of both players reduces by $\texttt{min(4, 2)} = 2$. The final health levels of Anna and Bob after the fight are $2$ and $0$ respectively.
- Fight $2$: Bob and Claudio fight. Thus, the health level of both players reduces by $\texttt{min(0, 0)} = 0$. The final health levels of Bob and Claudio after the fight are $0$ and $0$ respectively.
- Fight $3$: Anna and Claudio fight. Thus, the health level of both players reduces by $\texttt{min(2, 0)} = 0$. The final health levels of Anna and Claudio after the fight are $2$ and $0$ respectively.

Thus, in the above sequence of fights, Anna has a positive health remaining at the end.

Test case $2$: It can be shown that there exists no sequence of fights such that Anna has a positive health remaining at the end of the battle.

Test case $3$: Consider the following sequence of fights:
- Fight $1$: Bob and Claudio fight. Thus, the health level of both players reduces by $\texttt{min(1, 4)} = 1$. The final health levels of Bob and Claudio after the fight are $0$ and $3$ respectively.
- Fight $2$: Anna and Bob fight. Thus, the health level of both players reduces by $\texttt{min(5, 0)} = 0$. The final health levels of Anna and Bob after the fight are $5$ and $0$ respectively.
- Fight $3$: Anna and Claudio fight. Thus, the health level of both players reduces by $\texttt{min(5, 3)} = 3$. The final health levels of Anna and Claudio after the fight are $2$ and $0$ respectively.

Thus, in the above sequence of fights, Anna has a positive health remaining at the end.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As Kevin is in BigMan's house, suddenly a trap sends him onto a grid with n rows and m columns.

BigMan's trap is configured by two arrays: an array a_1,a_2,…,a_n and an array b_1,b_2,…,b_m.

In the i-th row there is a heater which heats the row by a_i degrees, and in the j-th column there is a heater which heats the column by b_j degrees, so that the temperature of cell (i,j) is a_i+b_j.

Fortunately, Kevin has a suit with one parameter x and two modes:

  * heat resistance. In this mode suit can stand all temperatures greater or equal to x, but freezes as soon as reaches a cell with temperature less than x. 
  * cold resistance. In this mode suit can stand all temperatures less than x, but will burn as soon as reaches a cell with temperature at least x.



Once Kevin lands on a cell the suit automatically turns to cold resistance mode if the cell has temperature less than x, or to heat resistance mode otherwise, and cannot change after that.

We say that two cells are adjacent if they share an edge.

Let a path be a sequence c_1,c_2,…,c_k of cells such that c_i and c_{i+1} are adjacent for 1 ≤ i ≤ k-1.

We say that two cells are connected if there is a path between the two cells consisting only of cells that Kevin can step on.

A connected component is a maximal set of pairwise connected cells.

We say that a connected component is good if Kevin can escape the grid starting from it — when it contains at least one border cell of the grid, and that it's bad otherwise.

To evaluate the situation, Kevin gives a score of 1 to each good component and a score of 2 for each bad component.

The final score will be the difference between the total score of components with temperatures bigger than or equal to x and the score of components with temperatures smaller than x.

There are q possible values of x that Kevin can use, and for each of them Kevin wants to know the final score.

Help Kevin defeat BigMan!

Input

The first line contains three integers n,m,q (1 ≤ n,m,q ≤ 10^5) – the number of rows, columns, and the number of possible values for x respectively.

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

The third line contains m integers b_1, b_2, ..., b_m (1 ≤ b_i ≤ 10^5).

Each of the next q lines contains one integer x (1 ≤ x ≤ 2 ⋅ 10^5).

Output

Output q lines, in the i-th line output the answer for the i-th possible value of x from the input.

Examples

Input


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


Output


-1


Input


3 3 2
1 2 2
2 1 2
3
4


Output


0
1

Note

In the first example, the score for components with temperature smaller than 5 is 1+2, and the score for components with temperature at least 5 is 2. Thus, the final score is 2-3=-1.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Recently Maxim has found an array of *n* integers, needed by no one. He immediately come up with idea of changing it: he invented positive integer *x* and decided to add or subtract it from arbitrary array elements. Formally, by applying single operation Maxim chooses integer *i* (1<=≤<=*i*<=≤<=*n*) and replaces the *i*-th element of array *a**i* either with *a**i*<=+<=*x* or with *a**i*<=-<=*x*. Please note that the operation may be applied more than once to the same position.

Maxim is a curious minimalis, thus he wants to know what is the minimum value that the product of all array elements (i.e. ) can reach, if Maxim would apply no more than *k* operations to it. Please help him in that.

Input Specification:
The first line of the input contains three integers *n*,<=*k* and *x* (1<=≤<=*n*,<=*k*<=≤<=200<=000,<=1<=≤<=*x*<=≤<=109) — the number of elements in the array, the maximum number of operations and the number invented by Maxim, respectively.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* () — the elements of the array found by Maxim.

Output Specification:
Print *n* integers *b*1,<=*b*2,<=...,<=*b**n* in the only line — the array elements after applying no more than *k* operations to the array. In particular,  should stay true for every 1<=≤<=*i*<=≤<=*n*, but the product of all array elements should be minimum possible.

If there are multiple answers, print any of them.

Demo Input:
['5 3 1\n5 4 3 5 2\n', '5 3 1\n5 4 3 5 5\n', '5 3 1\n5 4 4 5 5\n', '3 2 7\n5 4 2\n']

Demo Output:
['5 4 3 5 -1 \n', '5 4 0 5 5 \n', '5 1 4 5 5 \n', '5 11 -5 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N students and M checkpoints on the xy-plane.

The coordinates of the i-th student (1 \leq i \leq N) is (a_i,b_i), and the coordinates of the checkpoint numbered j (1 \leq j \leq M) is (c_j,d_j).

When the teacher gives a signal, each student has to go to the nearest checkpoint measured in Manhattan distance. 

The Manhattan distance between two points (x_1,y_1) and (x_2,y_2) is |x_1-x_2|+|y_1-y_2|.

Here, |x| denotes the absolute value of x.

If there are multiple nearest checkpoints for a student, he/she will select the checkpoint with the smallest index.

Which checkpoint will each student go to?

-----Constraints-----
 - 1 \leq N,M \leq 50
 - -10^8 \leq a_i,b_i,c_j,d_j \leq 10^8
 - All input values are integers.

-----Input-----
The input is given from Standard Input in the following format:
N M
a_1 b_1
:  
a_N b_N
c_1 d_1
:  
c_M d_M

-----Output-----
Print N lines.

The i-th line (1 \leq i \leq N) should contain the index of the checkpoint for the i-th student to go.

-----Sample Input-----
2 2
2 0
0 0
-1 0
1 0

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

The Manhattan distance between the first student and each checkpoint is:
 - For checkpoint 1: |2-(-1)|+|0-0|=3
 - For checkpoint 2: |2-1|+|0-0|=1
The nearest checkpoint is checkpoint 2. Thus, the first line in the output should contain 2.
The Manhattan distance between the second student and each checkpoint is:
 - For checkpoint 1: |0-(-1)|+|0-0|=1
 - For checkpoint 2: |0-1|+|0-0|=1
When there are multiple nearest checkpoints, the student will go to the checkpoint with the smallest index. Thus, the second line in the output should contain 1.

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