vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are n rabbits, one in each of the huts numbered 0 through n − 1.

At one point, information came to the rabbits that a secret organization would be constructing an underground passage. The underground passage would allow the rabbits to visit other rabbits' huts. I'm happy.

The passages can go in both directions, and the passages do not intersect. Due to various circumstances, the passage once constructed may be destroyed. The construction and destruction of the passages are carried out one by one, and each construction It is assumed that the rabbit stays in his hut.

Rabbits want to know in advance if one rabbit and one rabbit can play at some stage of construction. Rabbits are good friends, so they are free to go through other rabbit huts when they go out to play. Rabbits who like programming tried to solve a similar problem in the past, thinking that it would be easy, but they couldn't write an efficient program. Solve this problem instead of the rabbit.



Input

The first line of input is given n and k separated by spaces. 2 ≤ n ≤ 40 000, 1 ≤ k ≤ 40 000

In the following k lines, construction information and questions are combined and given in chronological order.

* “1 u v” — A passage connecting huts u and v is constructed. Appears only when there is no passage connecting huts u and v.
* “2 u v” — The passage connecting huts u and v is destroyed. Appears only when there is a passage connecting huts u and v.
* “3 u v” — Determine if the rabbits in the hut u and v can be played.



0 ≤ u <v <n

Output

For each question that appears in the input, output "YES" if you can play, or "NO" if not.

Example

Input

4 10
1 0 1
1 0 2
3 1 2
2 0 1
1 2 3
3 0 1
1 0 1
2 0 2
1 1 3
3 0 2


Output

YES
NO
YES

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There is a rectangular grid of *n* rows of *m* initially-white cells each.

Arkady performed a certain number (possibly zero) of operations on it. In the *i*-th operation, a non-empty subset of rows *R**i* and a non-empty subset of columns *C**i* are chosen. For each row *r* in *R**i* and each column *c* in *C**i*, the intersection of row *r* and column *c* is coloured black.

There's another constraint: a row or a column can only be chosen at most once among all operations. In other words, it means that no pair of (*i*,<=*j*) (*i*<=&lt;<=*j*) exists such that  or , where  denotes intersection of sets, and  denotes the empty set.

You are to determine whether a valid sequence of operations exists that produces a given final grid.

Input Specification:
The first line contains two space-separated integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=50) — the number of rows and columns of the grid, respectively.

Each of the following *n* lines contains a string of *m* characters, each being either '.' (denoting a white cell) or '#' (denoting a black cell), representing the desired setup.

Output Specification:
If the given grid can be achieved by any valid sequence of operations, output "Yes"; otherwise output "No" (both without quotes).

You can print each character in any case (upper or lower).

Demo Input:
['5 8\n.#.#..#.\n.....#..\n.#.#..#.\n#.#....#\n.....#..\n', '5 5\n..#..\n..#..\n#####\n..#..\n..#..\n', '5 9\n........#\n#........\n..##.#...\n.......#.\n....#.#.#\n']

Demo Output:
['Yes\n', 'No\n', 'No\n']

Note:
For the first example, the desired setup can be produced by 3 operations, as is shown below.

For the second example, the desired setup cannot be produced, since in order to colour the center row, the third row and all columns must be selected in one operation, but after that no column can be selected again, hence it won't be possible to colour the other cells in the center column.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's consider some integer X. We will call the following sequence S a sequence generated by X:
for i = 1: S[i] = X 
for i > 1: S[i] equals to the minimal positive integer such that S[i] is not a divisor of S[i - 1]. If there is no such integer than S[i - 1] is the last element of S.

For example S = (10, 3, 2) is a sequence generated by 10.

Can you find the total sum of lengths of the sequnces generated by all the integers from A  to B inclusive.

Input
The only line contains two integers: A and B. (A ≤ B)

Output 
Output the only integer - answer to the question. It's guaranteed that this value can be stored in 64-bit integer.

Constraints 
1 < A ≤ B ≤ 10^17

SAMPLE INPUT
2 6

SAMPLE OUTPUT
12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Appleman and a Sheet of Paper

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Appleman has a very big sheet of paper. This sheet has a form of rectangle with dimensions 1<=×<=*n*. Your task is help Appleman with folding of such a sheet. Actually, you need to perform *q* queries. Each query will have one of the following types:
 1.  Fold the sheet of paper at position *p**i*. After this query the leftmost part of the paper with dimensions 1<=×<=*p**i* must be above the rightmost part of the paper with dimensions 1<=×<=([*current* *width* *of* *sheet*]<=-<=*p**i*). 1.  Count what is the total width of the paper pieces, if we will make two described later cuts and consider only the pieces between the cuts. We will make one cut at distance *l**i* from the left border of the current sheet of paper and the other at distance *r**i* from the left border of the current sheet of paper. 
Please look at the explanation of the first test example for better understanding of the problem.

Input Specification:
The first line contains two integers: *n* and *q* (1<=<=≤<=*n*<=≤<=105; 1<=≤<=*q*<=≤<=105) — the width of the paper and the number of queries.

Each of the following *q* lines contains one of the described queries in the following format:
 -  "1 *p**i*" (1<=≤<=*p**i*<=&lt;<=[*current* *width* *of* *sheet*]) — the first type query. -  "2 *l**i* *r**i*" (0<=≤<=*l**i*<=&lt;<=*r**i*<=≤<=[*current* *width* *of* *sheet*]) — the second type query.

Output Specification:
For each query of the second type, output the answer.

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

Demo Output:
['4\n3\n', '7\n2\n10\n4\n5\n']

Note:
The pictures below show the shapes of the paper during the queries of the first example:

After the first fold operation the sheet has width equal to 4, after the second one the width of the sheet equals to 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The government of Berland decided to improve network coverage in his country. Berland has a unique structure: the capital in the center and $n$ cities in a circle around the capital. The capital already has a good network coverage (so the government ignores it), but the $i$-th city contains $a_i$ households that require a connection.

The government designed a plan to build $n$ network stations between all pairs of neighboring cities which will maintain connections only for these cities. In other words, the $i$-th network station will provide service only for the $i$-th and the $(i + 1)$-th city (the $n$-th station is connected to the $n$-th and the $1$-st city).

All network stations have capacities: the $i$-th station can provide the connection to at most $b_i$ households.

Now the government asks you to check can the designed stations meet the needs of all cities or not — that is, is it possible to assign each household a network station so that each network station $i$ provides the connection to at most $b_i$ households.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($2 \le n \le 10^6$) — the number of cities and stations.

The second line of each test case contains $n$ integers ($1 \le a_i \le 10^9$) — the number of households in the $i$-th city.

The third line of each test case contains $n$ integers ($1 \le b_i \le 10^9$) — the capacities of the designed stations.

It's guaranteed that the sum of $n$ over test cases doesn't exceed $10^6$.


-----Output-----

For each test case, print YES, if the designed stations can meet the needs of all cities, or NO otherwise (case insensitive).


-----Example-----
Input
5
3
2 3 4
3 3 3
3
3 3 3
2 3 4
4
2 3 4 5
3 7 2 2
4
4 5 2 3
2 3 2 7
2
1 1
10 10

Output
YES
YES
NO
YES
YES



-----Note-----

In the first test case:   the first network station can provide $2$ connections to the first city and $1$ connection to the second city;  the second station can provide $2$ connections to the second city and $1$ connection to the third city;  the third station can provide $3$ connections to the third city. 

In the second test case:   the $1$-st station can provide $2$ connections to the $1$-st city;  the $2$-nd station can provide $3$ connections to the $2$-nd city;  the $3$-rd station can provide $3$ connections to the $3$-rd city and $1$ connection to the $1$-st station. 

In the third test case, the fourth city needs $5$ connections, but the third and the fourth station has $4$ connections in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:


Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.


Example 2:


Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The programming competition season has already started and it's time to train for ICPC. Sereja coaches his teams for a number of year and he knows that to get ready for the training session it's not enough to prepare only problems and editorial. As the training sessions lasts for several hours, teams become hungry. Thus, Sereja orders a number of pizzas so they can eat right after the end of the competition.

Teams plan to train for n times during n consecutive days. During the training session Sereja orders exactly one pizza for each team that is present this day. He already knows that there will be a_{i} teams on the i-th day.

There are two types of discounts in Sereja's favourite pizzeria. The first discount works if one buys two pizzas at one day, while the second is a coupon that allows to buy one pizza during two consecutive days (two pizzas in total).

As Sereja orders really a lot of pizza at this place, he is the golden client and can use the unlimited number of discounts and coupons of any type at any days.

Sereja wants to order exactly a_{i} pizzas on the i-th day while using only discounts and coupons. Note, that he will never buy more pizzas than he need for this particular day. Help him determine, whether he can buy the proper amount of pizzas each day if he is allowed to use only coupons and discounts. Note, that it's also prohibited to have any active coupons after the end of the day n.


-----Input-----

The first line of input contains a single integer n (1 ≤ n ≤ 200 000) — the number of training sessions.

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10 000) — the number of teams that will be present on each of the days.


-----Output-----

If there is a way to order pizzas using only coupons and discounts and do not buy any extra pizzas on any of the days, then print "YES" (without quotes) in the only line of output. Otherwise, print "NO" (without quotes).


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

Output
YES

Input
3
1 0 1

Output
NO



-----Note-----

In the first sample, Sereja can use one coupon to buy one pizza on the first and the second days, one coupon to buy pizza on the second and the third days and one discount to buy pizzas on the fourth days. This is the only way to order pizzas for this sample.

In the second sample, Sereja can't use neither the coupon nor the discount without ordering an extra pizza. Note, that it's possible that there will be no teams attending the training sessions on some days.

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

There are N islands and M bridges. Numbers from 1 to N are assigned to each of the N islands. Numbers from 1 to M are also assigned to each of the M bridges.

Gaccho is currently on the first island (at time 0). Gaccho can move from the ai-th island to the bi-th island in one direction by using the i-th bridge.

However, at time 0, all the bridges were full of tide and sank into the sea. The i-th bridge will be able to cross the tide at time ci. And soon after the time ci, the tide rises again and the i-th bridge sinks again. When it sinks again, I don't know when the tide will pull and cross. So, Gaccho decided to think that such a bridge would never be crossed.

Gaccho wants to see the scenery of the 1st to N-1st islands for as long as possible, but since he is staying at the Nth island, he finally arrives at the Nth island. There must be. Also, because he keeps his parents waiting on the boat, Gacho must leave by boat and go home as soon as he arrives at the Nth island.

The time it takes for Gaccho to cross the bridge and travel around the island is very short, so you can assume it is 0. Find the maximum amount of time Gaccho can be on any of the 1st to N-1 islands. However, if you can't move to the Nth island no matter how you move, output -1 instead.

Constraints

* 2 ≤ N ≤ 105
* 1 ≤ M ≤ 2 × 105
* 1 ≤ ai <N
* 1 ≤ bi ≤ N
* 1 ≤ ci ≤ 109
* ai ≠ bi

Input

The input is given in the following format.


N M
a1 b1 c1
a2 b2 c2
...
aM bM cM


On the first line, two integers N and M are given, separated by blanks.
Three integers ai, bi, ci are given in each line i from the second line to the M + 1 line, separated by blanks.

Output

If Gaccho can move to the Nth island, it will output the maximum amount of time that Gaccho can be on any of the 1st to N-1th islands. If it cannot move to the Nth island, it prints -1 instead.

Examples

Input

3 2
1 2 10
2 3 20


Output

20


Input

4 4
1 2 27
1 3 37
2 3 47
3 1 57


Output

-1


Input

3 3
1 2 13
2 3 17
2 3 15


Output

17


Input

3 2
1 2 20
2 3 10


Output

-1


Input

3 2
1 2 10
2 3 10


Output

10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket. 

The goods in the supermarket have unique integer ids. Also, for every integer there is a product with id equal to this integer. Fedor has n discount coupons, the i-th of them can be used with products with ids ranging from l_{i} to r_{i}, inclusive. Today Fedor wants to take exactly k coupons with him.

Fedor wants to choose the k coupons in such a way that the number of such products x that all coupons can be used with this product x is as large as possible (for better understanding, see examples). Fedor wants to save his time as well, so he asks you to choose coupons for him. Help Fedor!


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 3·10^5) — the number of coupons Fedor has, and the number of coupons he wants to choose.

Each of the next n lines contains two integers l_{i} and r_{i} ( - 10^9 ≤ l_{i} ≤ r_{i} ≤ 10^9) — the description of the i-th coupon. The coupons can be equal.


-----Output-----

In the first line print single integer — the maximum number of products with which all the chosen coupons can be used. The products with which at least one coupon cannot be used shouldn't be counted.

In the second line print k distinct integers p_1, p_2, ..., p_{k} (1 ≤ p_{i} ≤ n) — the ids of the coupons which Fedor should choose.

If there are multiple answers, print any of them.


-----Examples-----
Input
4 2
1 100
40 70
120 130
125 180

Output
31
1 2 

Input
3 2
1 12
15 20
25 30

Output
0
1 2 

Input
5 2
1 10
5 15
14 50
30 70
99 100

Output
21
3 4 



-----Note-----

In the first example if we take the first two coupons then all the products with ids in range [40, 70] can be bought with both coupons. There are 31 products in total.

In the second example, no product can be bought with two coupons, that is why the answer is 0. Fedor can choose any two coupons in this example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an $array$ of size $N$ and an integer $K$ ( $N > 1 , K > 0$ ).
Each element in the array can be incremented by $K$ or decremented by $K$ $at$ $most$ $once$.
So there will be  $3^n$ possible combinations of final array. (As there are 3 options for every element).

Out of these combinations, you have to select a combination, in which the $absolute$ difference between the largest and the smallest element is $maximum$.
You have to print the $maximum$ $absolute$ $difference$.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a two lines of input
- First line contains two integers $N, K$. 
- Second line contains $N$ space separated integers.

-----Output:-----
For each testcase, output the maximum absolute difference that can be achieved on a new line.

-----Constraints-----
- $1 \leq T \leq 10$
- $2 \leq N \leq 1000$
- $1 \leq K , arr[i]  \leq 10000$
$NOTE$:  Large  input files, Use of fastio is recommended.

-----Sample Input:-----
2

4 3

4 2 5 1

3 5

2 5 3

-----Sample Output:-----
10

13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of n elements, where each element is at most k away from its target position, you need to sort the array optimally.
Example 1:
Input:
n = 7, k = 3
arr[] = {6,5,3,2,8,10,9}
Output: 2 3 5 6 8 9 10
Explanation: The sorted array will be
2 3 5 6 8 9 10
Example 2:
Input:
n = 5, k = 2
arr[] = {3,1,4,2,5}
Output: 1 2 3 4 5 
Note: DO NOT use STL sort() function for this question.
Your Task:
You are required to complete the method nearlySorted() which takes 3 arguments and returns the sorted array.
Expected Time Complexity : O(nlogk)
Expected Auxilliary Space : O(n)
Constraints:
1 ≤ n ≤ 10^{6}
1 ≤ k < n
1 ≤ arr_{i }≤ 10^{7}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a valid XML document, and you have to print the maximum level of nesting in it. Take the depth of the root as $\mbox{0}$.

Input Format

The first line contains $N$, the number of lines in the XML document. 

The next $N$ lines follow containing the XML document.

Output Format

Output a single line, the integer value of the maximum level of nesting in the XML document.

Sample Input  

6
<feed xml:lang='en'>
    <title>HackerRank</title>
    <subtitle lang='en'>Programming challenges</subtitle>
    <link rel='alternate' type='text/html' href='http://hackerrank.com/'/>
    <updated>2013-12-25T12:00:00</updated>
</feed>

Sample Output  

1

Explanation

Here, the root is a feed tag, which has depth of $\mbox{0}$. 

The tags title, subtitle, link and updated all have a depth of $\mbox{1}$. 

Thus, the maximum depth is $\mbox{1}$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There is an airplane which has *n* rows from front to back. There will be *m* people boarding this airplane.

This airplane has an entrance at the very front and very back of the plane.

Each person has some assigned seat. It is possible for multiple people to have the same assigned seat. The people will then board the plane one by one starting with person 1. Each person can independently choose either the front entrance or back entrance to enter the plane.

When a person walks into the plane, they walk directly to their assigned seat and will try to sit in it. If it is occupied, they will continue walking in the direction they walked in until they are at empty seat - they will take the earliest empty seat that they can find. If they get to the end of the row without finding a seat, they will be angry.

Find the number of ways to assign tickets to the passengers and board the plane without anyone getting angry. Two ways are different if there exists a passenger who chose a different entrance in both ways, or the assigned seat is different. Print this count modulo 109<=+<=7.

Input Specification:
The first line of input will contain two integers *n*,<=*m* (1<=≤<=*m*<=≤<=*n*<=≤<=1<=000<=000), the number of seats, and the number of passengers, respectively.

Output Specification:
Print a single number, the number of ways, modulo 109<=+<=7.

Demo Input:
['3 3\n']

Demo Output:
['128\n']

Note:
Here, we will denote a passenger by which seat they were assigned, and which side they came from (either "F" or "B" for front or back, respectively).

For example, one valid way is 3B, 3B, 3B (i.e. all passengers were assigned seat 3 and came from the back entrance). Another valid way would be 2F, 1B, 3F.

One invalid way would be 2B, 2B, 2B, since the third passenger would get to the front without finding a seat.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sereja owns a restaurant for *n* people. The restaurant hall has a coat rack with *n* hooks. Each restaurant visitor can use a hook to hang his clothes on it. Using the *i*-th hook costs *a**i* rubles. Only one person can hang clothes on one hook.

Tonight Sereja expects *m* guests in the restaurant. Naturally, each guest wants to hang his clothes on an available hook with minimum price (if there are multiple such hooks, he chooses any of them). However if the moment a guest arrives the rack has no available hooks, Sereja must pay a *d* ruble fine to the guest. 

Help Sereja find out the profit in rubles (possibly negative) that he will get tonight. You can assume that before the guests arrive, all hooks on the rack are available, all guests come at different time, nobody besides the *m* guests is visiting Sereja's restaurant tonight.

Input Specification:
The first line contains two integers *n* and *d* (1<=≤<=*n*,<=*d*<=≤<=100). The next line contains integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=100). The third line contains integer *m* (1<=≤<=*m*<=≤<=100).

Output Specification:
In a single line print a single integer — the answer to the problem.

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

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

Note:
In the first test both hooks will be used, so Sereja gets 1 + 2 = 3 rubles.

In the second test both hooks will be used but Sereja pays a fine 8 times, so the answer is 3 - 8 =  - 5.

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

HINT : Digital Display
Input :
First line has an integer T.
Next T lines has an integer N in each line. It is guaranteed that N never starts with 0 unless value is equal to zero.

Output :
Print the output for each test case in new line.

Constraints :
1 ≤ T ≤ 1000
0 ≤ |N| ≤ 1000
|N| is number of digits.

Problem Setter : Vinay Kumar

SAMPLE INPUT
8
1234567
123456
1234
193
12
11
1
0

SAMPLE OUTPUT
30
27
16
13
7
4
2
6

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