vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The mayor of the Central Town wants to modernize Central Street, represented in this problem by the (Ox) axis.

On this street, there are n antennas, numbered from 1 to n. The i-th antenna lies on the position x_i and has an initial scope of s_i: it covers all integer positions inside the interval [x_i - s_i; x_i + s_i].

It is possible to increment the scope of any antenna by 1, this operation costs 1 coin. We can do this operation as much as we want (multiple times on the same antenna if we want).

To modernize the street, we need to make all integer positions from 1 to m inclusive covered by at least one antenna. Note that it is authorized to cover positions outside [1; m], even if it's not required.

What is the minimum amount of coins needed to achieve this modernization?

Input

The first line contains two integers n and m (1 ≤ n ≤ 80 and n ≤ m ≤ 100\ 000).

The i-th of the next n lines contains two integers x_i and s_i (1 ≤ x_i ≤ m and 0 ≤ s_i ≤ m).

On each position, there is at most one antenna (values x_i are pairwise distinct).

Output

You have to output a single integer: the minimum amount of coins required to make all integer positions from 1 to m inclusive covered by at least one antenna.

Examples

Input


3 595
43 2
300 4
554 10


Output


281


Input


1 1
1 1


Output


0


Input


2 50
20 0
3 1


Output


30


Input


5 240
13 0
50 25
60 5
155 70
165 70


Output


26

Note

In the first example, here is a possible strategy:

  * Increase the scope of the first antenna by 40, so that it becomes 2 + 40 = 42. This antenna will cover interval [43 - 42; 43 + 42] which is [1; 85] 
  * Increase the scope of the second antenna by 210, so that it becomes 4 + 210 = 214. This antenna will cover interval [300 - 214; 300 + 214], which is [86; 514] 
  * Increase the scope of the third antenna by 31, so that it becomes 10 + 31 = 41. This antenna will cover interval [554 - 41; 554 + 41], which is [513; 595] 



Total cost is 40 + 210 + 31 = 281. We can prove that it's the minimum cost required to make all positions from 1 to 595 covered by at least one antenna.

Note that positions 513 and 514 are in this solution covered by two different antennas, but it's not important.

—

In the second example, the first antenna already covers an interval [0; 2] so we have nothing to do.

Note that the only position that we needed to cover was position 1; positions 0 and 2 are covered, but it's not important.

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 number of the positive divisors of N!, modulo 10^9+7.

-----Constraints-----
 - 1≤N≤10^3

-----Input-----
The input is given from Standard Input in the following format:
N

-----Output-----
Print the number of the positive divisors of N!, modulo 10^9+7.

-----Sample Input-----
3

-----Sample Output-----
4

There are four divisors of 3! =6: 1, 2, 3 and 6. Thus, the output should be 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once upon a time Petya and Gena gathered after another programming competition and decided to play some game. As they consider most modern games to be boring, they always try to invent their own games. They have only stickers and markers, but that won't stop them.

The game they came up with has the following rules. Initially, there are n stickers on the wall arranged in a row. Each sticker has some number written on it. Now they alternate turn, Petya moves first.

One move happens as follows. Lets say there are m ≥ 2 stickers on the wall. The player, who makes the current move, picks some integer k from 2 to m and takes k leftmost stickers (removes them from the wall). After that he makes the new sticker, puts it to the left end of the row, and writes on it the new integer, equal to the sum of all stickers he took on this move. 

Game ends when there is only one sticker left on the wall. The score of the player is equal to the sum of integers written on all stickers he took during all his moves. The goal of each player is to maximize the difference between his score and the score of his opponent.

Given the integer n and the initial sequence of stickers on the wall, define the result of the game, i.e. the difference between the Petya's and Gena's score if both players play optimally. 


-----Input-----

The first line of input contains a single integer n (2 ≤ n ≤ 200 000) — the number of stickers, initially located on the wall.

The second line contains n integers a_1, a_2, ..., a_{n} ( - 10 000 ≤ a_{i} ≤ 10 000) — the numbers on stickers in order from left to right.


-----Output-----

Print one integer — the difference between the Petya's score and Gena's score at the end of the game if both players play optimally.


-----Examples-----
Input
3
2 4 8

Output
14

Input
4
1 -7 -2 3

Output
-3



-----Note-----

In the first sample, the optimal move for Petya is to take all the stickers. As a result, his score will be equal to 14 and Gena's score will be equal to 0.

In the second sample, the optimal sequence of moves is the following. On the first move Petya will take first three sticker and will put the new sticker with value  - 8. On the second move Gena will take the remaining two stickers. The Petya's score is 1 + ( - 7) + ( - 2) =  - 8, Gena's score is ( - 8) + 3 =  - 5, i.e. the score difference will be  - 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
At the annual family gathering, the family likes to find the oldest living family member’s age and the youngest family member’s age and calculate the difference between them.

You will be given an array of all the family members' ages, in any order.  The ages will be given in whole numbers, so a baby of 5 months, will have an ascribed ‘age’ of 0.  Return a new array (a tuple in Python) with [youngest age, oldest age, difference between the youngest and oldest age].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Luba has to do n chores today. i-th chore takes a_{i} units of time to complete. It is guaranteed that for every $i \in [ 2 . . n ]$ the condition a_{i} ≥ a_{i} - 1 is met, so the sequence is sorted.

Also Luba can work really hard on some chores. She can choose not more than k any chores and do each of them in x units of time instead of a_{i} ($x < \operatorname{min}_{i = 1}^{n} a_{i}$).

Luba is very responsible, so she has to do all n chores, and now she wants to know the minimum time she needs to do everything. Luba cannot do two chores simultaneously.


-----Input-----

The first line contains three integers n, k, x (1 ≤ k ≤ n ≤ 100, 1 ≤ x ≤ 99) — the number of chores Luba has to do, the number of chores she can do in x units of time, and the number x itself.

The second line contains n integer numbers a_{i} (2 ≤ a_{i} ≤ 100) — the time Luba has to spend to do i-th chore.

It is guaranteed that $x < \operatorname{min}_{i = 1}^{n} a_{i}$, and for each $i \in [ 2 . . n ]$ a_{i} ≥ a_{i} - 1.


-----Output-----

Print one number — minimum time Luba needs to do all n chores.


-----Examples-----
Input
4 2 2
3 6 7 10

Output
13

Input
5 2 1
100 100 100 100 100

Output
302



-----Note-----

In the first example the best option would be to do the third and the fourth chore, spending x = 2 time on each instead of a_3 and a_4, respectively. Then the answer is 3 + 6 + 2 + 2 = 13.

In the second example Luba can choose any two chores to spend x time on them instead of a_{i}. So the answer is 100·3 + 2·1 = 302.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has the string s of length n consisted of digits 4 and 7.
The string s is called balanced
if there exits such integer x (1 ≤ x ≤ n) that the number of digits 4 in substring s[1; x) is equal to the number of digits 7 in substring s(x; n],
where s[1; x) is the substring from the 1st digit to (x-1)th digit of s, and s(x; n] is the substring from the (x+1)th digit to nth digit of s.
For example, s = 747474 is a balanced string, because s[1; 4) = 747 has one 4 and s(4; 6] = 74 has one 7.
Note that x can be 1 or n and s[1; 1) and s(n; n] denote an empty string.

In one turn Chef can choose any pair of consecutive digits and swap them.
Find for Chef the total number of different balanced string that can be obtained from string s using any (even 0) number of turns.
Print the result modulo 1000000007.

-----Input-----

The first line of the input contains one integer T, the number of test cases.
Then T lines follow, each of which contains string s for the corresponding test.

-----Output-----
T lines, each of which contains single integer - the answer for the corresponding test modulo 109+7.

-----Constraints-----

1 ≤ T ≤ 10

1 ≤ n ≤ 5000

-----Example-----
Input:
2
47
4477

Output:
1
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dolphin resides in two-dimensional Cartesian plane, with the positive x-axis pointing right and the positive y-axis pointing up.
Currently, he is located at the point (sx,sy). In each second, he can move up, down, left or right by a distance of 1.
Here, both the x- and y-coordinates before and after each movement must be integers.
He will first visit the point (tx,ty) where sx < tx and sy < ty, then go back to the point (sx,sy), then visit the point (tx,ty) again, and lastly go back to the point (sx,sy).
Here, during the whole travel, he is not allowed to pass through the same point more than once, except the points (sx,sy) and (tx,ty).
Under this condition, find a shortest path for him.

Constraints

* -1000 ≤ sx < tx ≤ 1000
* -1000 ≤ sy < ty ≤ 1000
* sx,sy,tx and ty are integers.

Input

The input is given from Standard Input in the following format:


sx sy tx ty


Output

Print a string S that represents a shortest path for Dolphin.
The i-th character in S should correspond to his i-th movement.
The directions of the movements should be indicated by the following characters:

* `U`: Up
* `D`: Down
* `L`: Left
* `R`: Right



If there exist multiple shortest paths under the condition, print any of them.

Examples

Input

0 0 1 2


Output

UURDDLLUUURRDRDDDLLU


Input

-2 -2 1 1


Output

UURRURRDDDLLDLLULUUURRURRDDDLLDL

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An SNS has N users - User 1, User 2, \cdots, User N.
Between these N users, there are some relationships - M friendships and K blockships.
For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.
For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.
We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:
 - a \neq b.
 - There is not a friendship between User a and User b.
 - There is not a blockship between User a and User b.
 - There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.
For each user i = 1, 2, ... N, how many friend candidates does it have?

-----Constraints-----
 - All values in input are integers.
 - 2 ≤ N ≤ 10^5
 - 0 \leq M \leq 10^5
 - 0 \leq K \leq 10^5
 - 1 \leq A_i, B_i \leq N
 - A_i \neq B_i
 - 1 \leq C_i, D_i \leq N
 - C_i \neq D_i
 - (A_i, B_i) \neq (A_j, B_j) (i \neq j)
 - (A_i, B_i) \neq (B_j, A_j)
 - (C_i, D_i) \neq (C_j, D_j) (i \neq j)
 - (C_i, D_i) \neq (D_j, C_j)
 - (A_i, B_i) \neq (C_j, D_j)
 - (A_i, B_i) \neq (D_j, C_j)

-----Input-----
Input is given from Standard Input in the following format:
N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

-----Output-----
Print the answers in order, with space in between.

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

-----Sample Output-----
0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.
However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A manufacturing project consists of exactly $K$ tasks. The board overviewing the project wants to hire $K$ teams of workers — one for each task. All teams begin working simultaneously.
Obviously, there must be at least one person in each team. For a team of $A$ workers, it takes exactly $A$ days to complete the task they are hired for. Each team acts independently, unaware of the status of other teams (whether they have completed their tasks or not), and submits their result for approval on the $A$-th day.
However, the board approves the project only if all $K$ teams complete their tasks on the same day — it rejects everything submitted on any other day. The day after a team finds out that its result was rejected, it resumes work on the same task afresh. Therefore, as long as a team of $A$ workers keeps getting rejected, it submits a new result of their task for approval on the $A$-th, $2A$-th, $3A$-th day etc.
The board wants to hire workers in such a way that it takes exactly $X$ days to complete the project. Find the smallest number of workers it needs to hire.

-----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 two space-separated integers $K$ and $X$.

-----Output-----
For each test case, print a single line containing one integer — the smallest required number of workers.

-----Constraints-----
- $1 \le T \le 40$
- $2 \le K, X \le 10^6$

-----Example Input-----
2
2 3
2 6

-----Example Output-----
4
5

-----Explanation-----
Example case 1: We can hire a team of $3$ workers for task $1$ and $1$ worker for task $2$. The one-man team working on task $2$ completes it and submits the result for approval on each day, but it is rejected on the first and second day. On the third day, the team working on task $1$ also completes their task, so the project gets approved after exactly $3$ days.
Example case 2: We can hire a team of $3$ workers for task $1$ and a team of $2$ workers for task $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are the boss of ACM (Air Conditioned Minions), an upstanding company with a single goal of world domination.

The company has $N$ minions. Each minion works evilly from early morning until evening inside a super secret bunker in Helsinki. After much deliberation, you decided to move your headquarters to Singapore. However, unlike Helsinki, Singapore is very hot, so the entire complex must be air conditioned. With strenuous working hours (under minimum wage too), it is imperative that all your minions work under optimal work condition. In particular, all minions must like the temperatures of the rooms they are in.

You are planning to construct several rooms in your new hideout, and assign your minions there. You fix the temperature of each room to any value you want (different rooms may have different temperatures). After you fix the temperatures, you will assign each of your minions to these rooms (a room can hold any number of minions). You want all minions to like the temperatures of their assigned rooms. Each minion likes an interval of temperature, and these preferences will be given to you.

Air conditioners are very expensive to maintain. Thus, you want to construct as few rooms as possible. What is the minimum number of rooms you need to set up such that it would be possible to assign minions to rooms as discussed earlier?

-----Input-----
The first line contains a non-negative integer $2 \leq N \leq 100$, giving the number of minions in your company. The next $N$ lines each describe the temperature preferences of all your minions. The $i$-th line consists of two single space separated integers $L$ and $U$ ($1 \le L \le U \le 2N$), which denotes that the $i$-th minion likes any temperature between $L$ and $U$, inclusively.

-----Output-----
Print an integer denoting the minimum number of rooms you need to construct.Sample Data Explanation

In the first example, one of the possible solutions is to setup two rooms — one with temperature $2$, and another with temperature $5$. The first two minions can be assigned to the first room, while the third minion can be assigned to the second room.

-----Examples-----
Sample Input:
3
1 2
2 4
5 6
Sample Output:
2

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

Let the i-th query query_i, the input format is following:



N Q
p_0 a_0
p_1 a_1
:   :
p_{N - 1} a_{N - 1}
query_0
query_1
:   :
query_{Q - 1}


THe format of query_i is one of the three format:



1 v_i d_i x_i



2 v_i d_i



3 pr_i ar_i


Output Format

Print the result in one line for each query 2.


Constraints

* N ≤ 400000
* Q ≤ 50000
* p_i < i for all valid i.
* In each question 1 or 2, worker v_i exists.
* d_i ≤ 400000
* 0 ≤ a_i, x_i ≤ 1000



Scoring

Subtask 1 [170 points]


* N, Q ≤ 5000

Subtask 2 [310 points]


* p_i + 1 = i for all valid i.

Subtask 3 [380 points]


* There are no query 3.

Subtask 4 [590 points]


* There are no additional constraints.



Sample Input 1


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


Sample Output 1


15
12
30
8

Output Format

Print the result in one line for each query 2.


Constraints

* N ≤ 400000
* Q ≤ 50000
* p_i < i for all valid i.
* In each question 1 or 2, worker v_i exists.
* d_i ≤ 400000
* 0 ≤ a_i, x_i ≤ 1000



Scoring

Subtask 1 [170 points]


* N, Q ≤ 5000

Subtask 2 [310 points]


* p_i + 1 = i for all valid i.

Subtask 3 [380 points]


* There are no query 3.

Subtask 4 [590 points]


* There are no additional constraints.

Input Format

Let the i-th query query_i, the input format is following:



N Q
p_0 a_0
p_1 a_1
:   :
p_{N - 1} a_{N - 1}
query_0
query_1
:   :
query_{Q - 1}


THe format of query_i is one of the three format:



1 v_i d_i x_i



2 v_i d_i



3 pr_i ar_i

Example

Input

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


Output

15
12
30
8

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kicker (table football) is a board game based on football, in which players control the footballers' figures mounted on rods by using bars to get the ball into the opponent's goal. When playing two on two, one player of each team controls the goalkeeper and the full-backs (plays defence), the other player controls the half-backs and forwards (plays attack).

Two teams of company Q decided to battle each other. Let's enumerate players from both teams by integers from 1 to 4. The first and second player play in the first team, the third and the fourth one play in the second team. For each of the four players we know their game skills in defence and attack. The defence skill of the *i*-th player is *a**i*, the attack skill is *b**i*.

Before the game, the teams determine how they will play. First the players of the first team decide who will play in the attack, and who will play in the defence. Then the second team players do the same, based on the choice of their opponents.

We will define a team's defence as the defence skill of player of the team who plays defence. Similarly, a team's attack is the attack skill of the player of the team who plays attack. We assume that one team is guaranteed to beat the other one, if its defence is strictly greater than the opponent's attack and its attack is strictly greater than the opponent's defence.

The teams of company Q know each other's strengths and therefore arrange their teams optimally. Identify the team that is guaranteed to win (if both teams act optimally) or tell that there is no such team.

Input Specification:
The input contain the players' description in four lines. The *i*-th line contains two space-separated integers *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=100) — the defence and the attack skill of the *i*-th player, correspondingly.

Output Specification:
If the first team can win, print phrase "Team 1" (without the quotes), if the second team can win, print phrase "Team 2" (without the quotes). If no of the teams can definitely win, print "Draw" (without the quotes).

Demo Input:
['1 100\n100 1\n99 99\n99 99\n', '1 1\n2 2\n3 3\n2 2\n', '3 3\n2 2\n1 1\n2 2\n']

Demo Output:
['Team 1\n', 'Team 2\n', 'Draw\n']

Note:
Let consider the first test sample. The first team can definitely win if it will choose the following arrangement: the first player plays attack, the second player plays defence.

Consider the second sample. The order of the choosing roles for players makes sense in this sample. As the members of the first team choose first, the members of the second team can beat them (because they know the exact defence value and attack value of the first team).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given a string and your task will be to return a list of ints detailing the count of uppercase letters, lowercase, numbers and special characters, as follows.

```Haskell
Solve("*'&ABCDabcde12345") = [4,5,5,3]. 
--the order is: uppercase letters, lowercase, numbers and special characters.
```

More examples in the test cases. 

Good luck!

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