vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Ant colony

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mole is hungry again. He found one ant colony, consisting of *n* ants, ordered in a row. Each ant *i* (1<=≤<=*i*<=≤<=*n*) has a strength *s**i*.

In order to make his dinner more interesting, Mole organizes a version of «Hunger Games» for the ants. He chooses two numbers *l* and *r* (1<=≤<=*l*<=≤<=*r*<=≤<=*n*) and each pair of ants with indices between *l* and *r* (inclusively) will fight. When two ants *i* and *j* fight, ant *i* gets one battle point only if *s**i* divides *s**j* (also, ant *j* gets one battle point only if *s**j* divides *s**i*). 

After all fights have been finished, Mole makes the ranking. An ant *i*, with *v**i* battle points obtained, is going to be freed only if *v**i*<==<=*r*<=-<=*l*, or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.

In order to choose the best sequence, Mole gives you *t* segments [*l**i*,<=*r**i*] and asks for each of them how many ants is he going to eat if those ants fight.

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=105), the size of the ant colony. 

The second line contains *n* integers *s*1,<=*s*2,<=...,<=*s**n* (1<=≤<=*s**i*<=≤<=109), the strengths of the ants. 

The third line contains one integer *t* (1<=≤<=*t*<=≤<=105), the number of test cases. 

Each of the next *t* lines contains two integers *l**i* and *r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*), describing one query.

Output Specification:
Print to the standard output *t* lines. The *i*-th line contains number of ants that Mole eats from the segment [*l**i*,<=*r**i*].

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

Demo Output:
['4\n4\n1\n1\n']

Note:
In the first test battle points for each ant are *v* = [4, 0, 2, 0, 2], so ant number 1 is freed. Mole eats the ants 2, 3, 4, 5.

In the second test case battle points are *v* = [0, 2, 0, 2], so no ant is freed and all of them are eaten by Mole.

In the third test case battle points are *v* = [2, 0, 2], so ants number 3 and 5 are freed. Mole eats only the ant 4.

In the fourth test case battle points are *v* = [0, 1], so ant number 5 is freed. Mole eats the ant 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set of n vectors on a plane. For each vector you are allowed to multiply any of its coordinates by -1. Thus, each vector vi = (xi, yi) can be transformed into one of the following four vectors:

  * vi1 = (xi, yi), 
  * vi2 = ( - xi, yi), 
  * vi3 = (xi, - yi), 
  * vi4 = ( - xi, - yi). 



You should find two vectors from the set and determine which of their coordinates should be multiplied by -1 so that the absolute value of the sum of the resulting vectors was minimally possible. More formally, you should choose two vectors vi, vj (1 ≤ i, j ≤ n, i ≠ j) and two numbers k1, k2 (1 ≤ k1, k2 ≤ 4), so that the value of the expression |vik1 + vjk2| were minimum.

Input

The first line contains a single integer n (2 ≤ n ≤ 105). Then n lines contain vectors as pairs of integers "xi yi" ( - 10000 ≤ xi, yi ≤ 10000), one pair per line.

Output

Print on the first line four space-separated numbers "i k1 j k2" — the answer to the problem. If there are several variants the absolute value of whose sums is minimum, you can print any of them. 

Examples

Input

5
-7 -3
9 0
-8 6
7 -8
4 -5


Output

3 2 4 2


Input

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


Output

3 4 5 4

Note

A sum of two vectors v = (xv, yv) and u = (xu, yu) is vector s = v + u = (xv + xu, yv + yu).

An absolute value of vector v = (x, y) is number <image>. 

In the second sample there are several valid answers, such as:

(3 1 4 2), (3 1 4 4), (3 4 4 1), (3 4 4 3), (4 1 3 2), (4 1 3 4), (4 2 3 1).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes A = {a1, a2, ..., an}, where the width and the height of the i-th envelope is strictly higher than the width and the height of the (i - 1)-th envelope respectively. Chain size is the number of envelopes in the chain. 

Peter wants to make the chain of the maximum size from the envelopes he has, the chain should be such, that he'll be able to put a card into it. The card fits into the chain if its width and height is lower than the width and the height of the smallest envelope in the chain respectively. It's forbidden to turn the card and the envelopes. 

Peter has very many envelopes and very little time, this hard task is entrusted to you.

Input

The first line contains integers n, w, h (1 ≤ n ≤ 5000, 1 ≤ w, h ≤ 106) — amount of envelopes Peter has, the card width and height respectively. Then there follow n lines, each of them contains two integer numbers wi and hi — width and height of the i-th envelope (1 ≤ wi, hi ≤ 106).

Output

In the first line print the maximum chain size. In the second line print the numbers of the envelopes (separated by space), forming the required chain, starting with the number of the smallest envelope. Remember, please, that the card should fit into the smallest envelope. If the chain of maximum size is not unique, print any of the answers.

If the card does not fit into any of the envelopes, print number 0 in the single line.

Examples

Input

2 1 1
2 2
2 2


Output

1
1 


Input

3 3 3
5 4
12 11
9 8


Output

3
1 3 2 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a directed weighted graph with n nodes and 2n - 2 edges. The nodes are labeled from 1 to n, while the edges are labeled from 1 to 2n - 2. The graph's edges can be split into two parts.

  * The first n - 1 edges will form a rooted spanning tree, with node 1 as the root. All these edges will point away from the root. 
  * The last n - 1 edges will be from node i to node 1, for all 2 ≤ i ≤ n. 



You are given q queries. There are two types of queries

  * 1 i w: Change the weight of the i-th edge to w
  * 2 u v: Print the length of the shortest path between nodes u to v



Given these queries, print the shortest path lengths.

Input

The first line of input will contain two integers n, q (2 ≤ n, q ≤ 200 000), the number of nodes, and the number of queries, respectively.

The next 2n - 2 integers will contain 3 integers ai, bi, ci, denoting a directed edge from node ai to node bi with weight ci.

The first n - 1 of these lines will describe a rooted spanning tree pointing away from node 1, while the last n - 1 of these lines will have bi = 1.

More specifically, 

  * The edges (a1, b1), (a2, b2), ... (an - 1, bn - 1) will describe a rooted spanning tree pointing away from node 1. 
  * bj = 1 for n ≤ j ≤ 2n - 2. 
  * an, an + 1, ..., a2n - 2 will be distinct and between 2 and n. 



The next q lines will contain 3 integers, describing a query in the format described in the statement.

All edge weights will be between 1 and 106.

Output

For each type 2 query, print the length of the shortest path in its own line.

Example

Input

5 9
1 3 1
3 2 2
1 4 3
3 5 4
5 1 5
3 1 6
2 1 7
4 1 8
2 1 1
2 1 3
2 3 5
2 5 2
1 1 100
2 1 3
1 8 30
2 4 2
2 2 4


Output

0
1
4
8
100
132
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya got really tired of these credits (from problem F) and now wants to earn the money himself! He decided to make a contest to gain a profit.

Vasya has $n$ problems to choose from. They are numbered from $1$ to $n$. The difficulty of the $i$-th problem is $d_i$. Moreover, the problems are given in the increasing order by their difficulties. The difficulties of all tasks are pairwise distinct. In order to add the $i$-th problem to the contest you need to pay $c_i$ burles to its author. For each problem in the contest Vasya gets $a$ burles.

In order to create a contest he needs to choose a consecutive subsegment of tasks.

So the total earnings for the contest are calculated as follows:   if Vasya takes problem $i$ to the contest, he needs to pay $c_i$ to its author;  for each problem in the contest Vasya gets $a$ burles;  let $gap(l, r) = \max\limits_{l \le i < r} (d_{i + 1} - d_i)^2$. If Vasya takes all the tasks with indices from $l$ to $r$ to the contest, he also needs to pay $gap(l, r)$. If $l = r$ then $gap(l, r) = 0$. 

Calculate the maximum profit that Vasya can earn by taking a consecutive segment of tasks.


-----Input-----

The first line contains two integers $n$ and $a$ ($1 \le n \le 3 \cdot 10^5$, $1 \le a \le 10^9$) — the number of proposed tasks and the profit for a single problem, respectively.

Each of the next $n$ lines contains two integers $d_i$ and $c_i$ ($1 \le d_i, c_i \le 10^9, d_i < d_{i+1}$).


-----Output-----

Print one integer — maximum amount of burles Vasya can earn.


-----Examples-----
Input
5 10
1 15
5 3
6 11
7 2
11 22

Output
13

Input
3 5
1 8
2 19
3 11

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A population of bears consists of black bears, brown bears, and white bears.

The input is an array of two elements. 

Determine whether the offspring of the two bears will return `'black'`, `'brown'`, `'white'`, `'dark brown'`, `'grey'`, `'light brown'`, or `'unknown'`.

Elements in the the array will always be a string.



## Examples:

    bear_fur(['black', 'black'])  returns 'black'

    bear_fur(['brown', 'brown'])  returns 'brown'

    bear_fur(['white', 'white'])  returns 'white'

    bear_fur(['black', 'brown'])  returns 'dark brown'

    bear_fur(['black', 'white'])  returns 'grey'

    bear_fur(['brown', 'white'])  returns 'light brown'

    bear_fur(['yellow', 'magenta'])  returns 'unknown'

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given a string of dominos. For each slot, there are 3 options:

  * "|" represents a standing domino

  * "/" represents a knocked over domino

  * " " represents a space where there is no domino

For example: 

```python
"||| ||||//| |/"
```

What you must do is find the resulting string if the first domino is pushed over. Now, tipping a domino will cause the next domino to its right to fall over as well, but if a domino is already tipped over, or there is a domino missing, the reaction will stop.

So in out example above, the result would be:

"/// ||||//| |/"

since the reaction would stop as soon as it gets to a space.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two integers A and B, return any string S such that:

S has length A + B and contains exactly A 'a' letters, and exactly B 'b' letters;
The substring 'aaa' does not occur in S;
The substring 'bbb' does not occur in S.

 
Example 1:
Input: A = 1, B = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.


Example 2:
Input: A = 4, B = 1
Output: "aabaa"
 

Note:

0 <= A <= 100
0 <= B <= 100
It is guaranteed such an S exists for the given A and B.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got an array *a*, consisting of *n* integers. The array elements are indexed from 1 to *n*. Let's determine a two step operation like that:
 1.  First we build by the array *a* an array *s* of partial sums, consisting of *n* elements. Element number *i* (1<=≤<=*i*<=≤<=*n*) of array *s* equals . The operation *x* *mod* *y* means that we take the remainder of the division of number *x* by number *y*. 1.  Then we write the contents of the array *s* to the array *a*. Element number *i* (1<=≤<=*i*<=≤<=*n*) of the array *s* becomes the *i*-th element of the array *a* (*a**i*<==<=*s**i*). 
You task is to find array *a* after exactly *k* described operations are applied.

Input Specification:
The first line contains two space-separated integers *n* and *k* (1<=≤<=*n*<=≤<=2000, 0<=≤<=*k*<=≤<=109). The next line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* — elements of the array *a* (0<=≤<=*a**i*<=≤<=109).

Output Specification:
Print *n* integers  — elements of the array *a* after the operations are applied to it. Print the elements in the order of increasing of their indexes in the array *a*. Separate the printed numbers by spaces.

Demo Input:
['3 1\n1 2 3\n', '5 0\n3 14 15 92 6\n']

Demo Output:
['1 3 6\n', '3 14 15 92 6\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the number of sequences of length K consisting of positive integers such that the product of any two adjacent elements is at most N, modulo 10^9+7.

Constraints

* 1\leq N\leq 10^9
* ~~1~~ 2\leq K\leq 100 (fixed at 21:33 JST)
* N and K are integers.

Input

Input is given from Standard Input in the following format:


N K


Output

Print the number of sequences, modulo 10^9+7.

Examples

Input

3 2


Output

5


Input

10 3


Output

147


Input

314159265 35


Output

457397712

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Daanish as always is busy creating and solving his favourite and interesting graph problems. Chef assigns each problem a difficulty — an integer between $1$ and $10$. For each valid $i$, there are $A_{i}$ problems with difficulty $i$.

A participant hacked Daanish's account and got access to the problem proposal document. He can delete up to $K$ problems from the document in order to reduce the difficulty of the contest for himself and his friends. Find the smallest possible value of the difficulty of the most difficult problem which remains after removing $K$ problems.

------  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 $10$ space-separated integers $A_{1}, A_{2}, \ldots, A_{10}$.
The second line contains a single integer $K$.

------  Output ------
For each test case, print a single line containing one integer — the minimum difficulty of the most difficult remaining problem.

------  Constraints ------
$1 ≤ T ≤ 2 \cdot 10^{4}$
$0 ≤ A_{i} ≤ 10^{8}$ for each valid $i$
$A_{1} + A_{2} + \ldots + A_{10} > 0$
$0 ≤ K < A_{1} + A_{2} + \ldots + A_{10}$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
5

1 10 1 5 3 2 4 9 0 100

100

2 0 1 0 0 0 0 0 0 10

12

2 0 1 0 0 0 0 10 0 0

0

2 0 1 0 0 0 0 0 0 10

10

1 10 1 5 3 2 4 9 0 100

125
----- Sample Output 1 ------ 
8

1

8

3

2
----- explanation 1 ------ 
Example case 1: The participant can remove all $100$ problems with difficulty $10$. Then, there are no problems with difficulties $9$ and $10$, so the maximum difficulty among remaining problems is $8$.

Example case 2: The participant can remove all problems with difficulties $3$ and $10$ and any one of the problems with difficulty $1$. Then, the only problem left has difficulty $1$.

Example case 3: The participant cannot remove any problem. The document does not contain any problems with difficulties $9$ or $10$, so the maximum difficulty of a problem is $8$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sequence of N elements, Chef defines a function F(i) (1 ≤ i ≤ N) as the median of the first i elements of the sequence.

Chef wants to get a *permutation* P of length N such that P_{i} = F(i) \forall 1 ≤ i ≤ N. Can you help Chef in achieving this?

Note that:
The *median* of a sequence is the middle element in the sorted order of the sequence. If N is even, choose the element at \frac{N}{2} position in the sorted order. If N is odd, choose the middle element.
A *permutation* of length N is an array of N integers P = [P_{1}, P_{2}, \ldots, P_{N}] such that every integer from 1 to N (inclusive) appears in it exactly once. For example, [2,5,4,1,3] is a permutation of length 5 while [2, 5, 2, 1, 3] is not.

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

- First line will contain T, number of test cases. Then the test cases follows.
- Each test case consists of a single line of input, an integer N, the length of the required permutation.

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

For each test case, output in a new line, N space-separated integers, denoting a *permutation* satisfying the condition.

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

$1 ≤ T ≤ 700$
$1 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

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

----- Sample Output 1 ------ 
1
2 1 
3 1 2
----- explanation 1 ------ 
Test Case $1$: $[1]$ is the only permutation and it satisfies the condition as the median of the sequence $[1]$ is $1$.

Test Case $2$: The possible permutations of length $2$ are $[1, 2]$ and $[2, 1]$. The only permutation that satisfies the condition is $[2, 1]$. Here, $P_{1} = 2 = median([2])$ and $P_{2} = 1 = median([2, 1])$.

Test Case $3$: There are $6$ possible permutations out of which only $[3,1,2]$ satisfies the above condition.  Here, $P_{1} = 3 = median([3]), P_{2} = 1 = median([3, 1]),$ and $P_{3} = 2 = median([3, 1, 2])$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef and his competitor Kefa own two restaurants located at a straight road. The position of Chef's restaurant is $X_1$, the position of Kefa's restaurant is $X_2$.
Chef and Kefa found out at the same time that a bottle with a secret recipe is located on the road between their restaurants. The position of the bottle is $X_3$.
The cooks immediately started to run to the bottle. Chef runs with speed $V_1$, Kefa with speed $V_2$.
Your task is to figure out who reaches the bottle first and gets the secret recipe (of course, it is possible that both cooks reach the bottle at the same time).

-----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 and only line of each test case contains five space-separated integers $X_1$, $X_2$, $X_3$, $V_1$ and $V_2$. 

-----Output-----
For each test case, print a single line containing the string "Chef" if Chef reaches the bottle first, "Kefa" if Kefa reaches the bottle first or "Draw" if Chef and Kefa reach the bottle at the same time (without quotes). 

-----Constraints-----
- $1 \le T \le 10^5$
- $|X_1|, |X_2|, |X_3| \le 10^5$
- $X_1 < X_3 < X_2$
- $1 \le V_1 \le 10^5$
- $1 \le V_2 \le 10^5$

-----Example Input-----
3
1 3 2 1 2
1 5 2 1 2
1 5 3 2 2

-----Example Output-----
Kefa
Chef
Draw

-----Explanation-----
Example case 1. Chef and Kefa are on the same distance from the bottle, but Kefa has speed $2$, while Chef has speed $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr[] of N integers, the task is to find a subsequence of size K whose product is maximum among all possible K sized subsequences of a given array.
Example 1:
Input: N = 4, K = 2
arr[] = {1, 2, 0, 3} 
Output: 6
Explanation: Subsequence containing 
elements {2, 3} gives maximum product: 
2*3 = 6
Example 2:
Input: N = 6, K = 4
arr[] = {1, 2, -1, -3, -6, 4}
Output: 144
Explanation: Subsequence containing 
{2, -3, -6, 4} gives maximum product: 
2*(-3)*(-6)*4 = 144
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 maxProductSubarrayOfSizeK() that takes array arr[], integer N and integer K as parameters and returns the desired product.
 
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are three people sitting in a room - Alice, Bob, and Charlie. They need to decide on the temperature to set on the air conditioner. Everyone has a demand each:

Alice wants the temperature to be at least A degrees.
Bob wants the temperature to be at most B degrees.
Charlie wants the temperature to be at least C degrees.

Can they all agree on some temperature, or not?

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line which contains three integers - A, B, C.

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

For each test case, output on a new line, "Yes" or "No". "Yes", if they can decide on some temperature which fits all their demands. Or "No", if no temperature fits all their demands.

You may print each character of the string in either uppercase or lowercase (for example, the strings NO, nO, No, and no will all be treated as identical).

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

$1 ≤ T ≤ 100$
$1 ≤ A, B, C ≤ 100$

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
4
30 35 25
30 35 40
30 35 35
30 25 35

----- Sample Output 1 ------ 
Yes
No
Yes
No

----- explanation 1 ------ 
Test Case 1: Alice wants the temperature to be $≥ 30$, Bob wants it to be $≤ 35$, and Charlie wants it to be $≥ 25$. The temperatures $30, 31, 32, 33, 34, 35$ all satisfy all their demands. So they can choose any of these 6 temperatures, and so the answer is "Yes".

Test Case 2: Alice wants the temperature to be $≥ 30$, Bob wants it to be $≤ 35$, and Charlie wants it to be $≥ 40$. A number can't be both $≥ 40$, and $≤ 35$. So there is no temperature that satisfies all their demands. So the answer is "No".

Test Case 3: Alice wants the temperature to be $≥ 30$, Bob wants it to be $≤ 35$, and Charlie wants it to be $≥ 35$. The temperature $35$ satisfies all their demands. So the answer is "Yes".

Test Case 4: Alice wants the temperature to be $≥ 30$, Bob wants it to be $≤ 25$, and Charlie wants it to be $≥ 35$. A number can't be both $≥ 30$, and $≤ 25$. So there is no temperature that satisfies all their demands. So the answer is "No".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number S, you need to check whether any permutation of the number S divisible by 8 or not. 
Example 1:
Input: S = "80"
Output: "Divisible"
Explanation: 80 is divisible by 8
Example 2
Input: S = "101"
Output: "Not divisible"
Your Task :
Complete the function isDivisible8() that receives a string S denoting the number and returns 1 if any permutation of the number is divisible by 8 or else returns 0.
Expected Time Complexity : O(lS|^{3})
Expected Space Complexity : O(1)
Constraints:
1 ≤ lS| ≤ 10^{2}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mira is very fond of gifts, so this valentine-season, Krish is going to gift her a game Nice Quadrilaterals (Yeah! Krish is such a geek!).
The game shows a convex Polygon of N-sides. And the game defines a Nice Quadrilateral as 
  "A quadrilateral made up of points from the given N-Polygon and which shares At least 2 edges to the original Polygon". 
Now given a convex N-polygon, Mira has to answer how many Nice Quadrilaterals she can draw.

Mira is not in a mood to start with this geek-freak game so she asks for your help. 

Input:

 First line with a T, the number of test cases.
 Then T lines follow, each with a number N.

Output:

 For each test case, output the Number of Nice Quadrilaterals for given N, on a new line.

Constraints:

  1 ≤ T ≤ 100000
   0 ≤ N ≤ 10^9+7;

SAMPLE INPUT
3
4
5
6

SAMPLE OUTPUT
1
5
15

Explanation

Case 1: for N=4, only one Nice Quadrilateral is possible.

Case 2 and Case 3: For N=5 or N=6, selecting any 4 points will give at least 2 edges from the original Polygon.

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