vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In distant future on Earth day lasts for n hours and that's why there are n timezones. Local times in adjacent timezones differ by one hour. For describing local time, hours numbers from 1 to n are used, i.e. there is no time "0 hours", instead of it "n hours" is used. When local time in the 1-st timezone is 1 hour, local time in the i-th timezone is i hours.

Some online programming contests platform wants to conduct a contest that lasts for an hour in such a way that its beginning coincides with beginning of some hour (in all time zones). The platform knows, that there are a_{i} people from i-th timezone who want to participate in the contest. Each person will participate if and only if the contest starts no earlier than s hours 00 minutes local time and ends not later than f hours 00 minutes local time. Values s and f are equal for all time zones. If the contest starts at f hours 00 minutes local time, the person won't participate in it.

Help platform select such an hour, that the number of people who will participate in the contest is maximum. 


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 100 000) — the number of hours in day.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10 000), where a_{i} is the number of people in the i-th timezone who want to participate in the contest.

The third line contains two space-separated integers s and f (1 ≤ s < f ≤ n).


-----Output-----

Output a single integer — the time of the beginning of the contest (in the first timezone local time), such that the number of participants will be maximum possible. If there are many answers, output the smallest among them.


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

Output
3

Input
5
1 2 3 4 1
1 3

Output
4



-----Note-----

In the first example, it's optimal to start competition at 3 hours (in first timezone). In this case, it will be 1 hour in the second timezone and 2 hours in the third timezone. Only one person from the first timezone won't participate.

In second example only people from the third and the fourth timezones will participate.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently, Polycarp has invented a new mobile game with falling blocks.

In the game, n blocks are falling down, one at a time, towards a flat surface with length d units. Each block can be represented as a rectangle with coordinates from l_i to r_i and unit height, dropped downwards from very high up. A block falls until it comes in contact with the flat surface or any other block. Let's define that block a covers block b if l_a ≤ l_b ≤ r_b ≤ r_a. 

Consider what happens when a new block i falls. If the new (upper) block i comes in contact with any block j such that block i does not cover block j, block i will stick to block j, and no blocks will disappear. Otherwise, all blocks that block i covers and is in contact with will be vaporized, and block i will continue falling with the ability to vaporize lower blocks.

For example, consider what happens when three blocks (1,2), (2,3) and (1,3) fall, in that order. The first block will stick to the flat surface. Then, the second block will stick to the first block. Finally, the third block will vaporize the second block, keep falling, vaporize the first block, and stick to the flat surface.

<image> Here is a graphic for the first example.

After each block falls, help Polycarp determine how many blocks will remain!

Input

The first line contains two integers n and d (1 ≤ n, d ≤ 10^5) — the number of falling blocks and the length of the flat surface.

The i-th of the following n lines contains integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ d) — the coordinates of the i-th block. 

Output

Output n integers. The i-th integer should be the number of blocks that will be left after the i-th block falls.

Examples

Input


3 3
1 2
2 3
1 3


Output


1
2
1


Input


8 6
1 2
3 3
2 3
1 3
2 4
3 6
1 5
1 5


Output


1
2
3
1
2
3
4
4

Note

The first example is explained above.

In the second example, this is what happens after each block falls: 

  * Block 1 will stick to the flat surface. 
  * Block 2 will stick to the flat surface. 
  * Block 3 will stick to blocks 1 and 2. Note that block 3 will not vaporize block 2 because it does not cover block 1 and is in contact with it. 
  * Block 4 will vaporize all the blocks and stick to the flat surface. 
  * Block 5 will stick to block 4 
  * Block 6 will stick to block 5. 
  * Block 7 will stick to block 6. Note that no blocks are vaporized because although block 7 covers block 4 and block 5, they never come in contact. 
  * Block 8 vaporizes block 7 and sticks to block 6. 

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Find the number of *k*-divisible numbers on the segment [*a*,<=*b*]. In other words you need to find the number of such integer values *x* that *a*<=≤<=*x*<=≤<=*b* and *x* is divisible by *k*.

Input Specification:
The only line contains three space-separated integers *k*, *a* and *b* (1<=≤<=*k*<=≤<=1018;<=-<=1018<=≤<=*a*<=≤<=*b*<=≤<=1018).

Output Specification:
Print the required number.

Demo Input:
['1 1 10\n', '2 -4 4\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a problem that involves adding numbers to items in a list.
In a list you will have to add the item's remainder when divided by a given divisor to each item.

For example if the item is 40 and the divisor is 3 you would have to add 1 since 40 minus the closest multiple of 3 which is 39 is 1. So the 40 in the list will become 41. You would have to return the modified list in this problem.

For this problem you will receive a divisor called `div` as well as simple list of whole numbers called `nums`. Good luck and happy coding.

# Examples
```python
nums = [2, 7, 5, 9, 100, 34, 32, 0], div = 3
  ==>  [4, 8, 7, 9, 101, 35, 34, 0] 

nums = [1000, 999, 998, 997], div = 5
   ==> [1000, 1003, 1001, 999]

nums = [], div = 2
   ==> []
```

**Note:** random tests check lists containing up to 10000 elements.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two arrays a[] and b[] of size n and m respectively. The task is to find the number of elements in the union between these two arrays. 
Union of the two arrays can be defined as the set containing distinct elements from both the arrays. If there are repetitions, then only one occurrence of element should be printed in the union.
Note : Elements are not necessarily distinct.
Example 1:
Input:
5 3
1 2 3 4 5
1 2 3
Output: 
5
Explanation: 
1, 2, 3, 4 and 5 are the
elements which comes in the union set
of both arrays. So count is 5.
Example 2:
Input:
6 2 
85 25 1 32 54 6
85 2 
Output: 
7
Explanation: 
85, 25, 1, 32, 54, 6, and
2 are the elements which comes in the
union set of both arrays. So count is 7.
Your Task:
Complete doUnion funciton that takes a, n, b, m as parameters and returns the count of union elements of the two arrays. The printing is done by the driver code.
Constraints:
1 ≤ n, m ≤ 10^{5}
0 ≤ a[i], b[i] < 10^{5}
Expected Time Complexity : O(n+m)
Expected Auxilliary Space : O(n+m)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Grigory has $n$ magic stones, conveniently numbered from $1$ to $n$. The charge of the $i$-th stone is equal to $c_i$.

Sometimes Grigory gets bored and selects some inner stone (that is, some stone with index $i$, where $2 \le i \le n - 1$), and after that synchronizes it with neighboring stones. After that, the chosen stone loses its own charge, but acquires the charges from neighboring stones. In other words, its charge $c_i$ changes to $c_i' = c_{i + 1} + c_{i - 1} - c_i$.

Andrew, Grigory's friend, also has $n$ stones with charges $t_i$. Grigory is curious, whether there exists a sequence of zero or more synchronization operations, which transforms charges of Grigory's stones into charges of corresponding Andrew's stones, that is, changes $c_i$ into $t_i$ for all $i$?


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 10^5$) — the number of magic stones.

The second line contains integers $c_1, c_2, \ldots, c_n$ ($0 \le c_i \le 2 \cdot 10^9$) — the charges of Grigory's stones.

The second line contains integers $t_1, t_2, \ldots, t_n$ ($0 \le t_i \le 2 \cdot 10^9$) — the charges of Andrew's stones.


-----Output-----

If there exists a (possibly empty) sequence of synchronization operations, which changes all charges to the required ones, print "Yes".

Otherwise, print "No".


-----Examples-----
Input
4
7 2 4 12
7 15 10 12

Output
Yes

Input
3
4 4 4
1 2 3

Output
No



-----Note-----

In the first example, we can perform the following synchronizations ($1$-indexed):  First, synchronize the third stone $[7, 2, \mathbf{4}, 12] \rightarrow [7, 2, \mathbf{10}, 12]$.  Then synchronize the second stone: $[7, \mathbf{2}, 10, 12] \rightarrow [7, \mathbf{15}, 10, 12]$. 

In the second example, any operation with the second stone will not change its charge.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once again, we have a lot of requests from coders for a challenging problem on geometry. Geometry expert Nitin is thinking about a problem with parabolas, icosahedrons, crescents and trapezoids, but for now, to encourage beginners, he chooses to work with circles and rectangles.
You are given two sequences $A_1, A_2, \ldots, A_N$ and $B_1, B_2, \ldots, B_N$. You should choose a permutation $P_1, P_2, \ldots, P_N$ of the integers $1$ through $N$ and construct $N$ rectangles with dimensions $A_1 \times B_{P_1}, A_2 \times B_{P_2}, \ldots, A_N \times B_{P_N}$. Then, for each of these rectangles, you should construct an inscribed circle, i.e. a circle with the maximum possible area that is completely contained in that rectangle.
Let $S$ be the sum of diameters of these $N$ circles. Your task is to find the maximum value of $S$.

-----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 a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$. 
- The third line contains $N$ space-separated integers $B_1, B_2, \ldots, B_N$. 

-----Output-----
For each test case, print a single line containing one integer ― the maximum value of $S$. It is guaranteed that this value is always an integer.

-----Constraints-----
- $1 \le T \le 50$
- $1 \le N \le 10^4$
- $1 \le A_i, B_i \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (20 points):
- $A_1 = A_2 = \ldots = A_N$
- $B_1 = B_2 = \ldots = B_N$
Subtask #2 (80 points): original constraints

-----Example Input-----
2
4
8 8 10 12
15 20 3 5
3
20 20 20
10 10 10

-----Example Output-----
30
30

-----Explanation-----
Example case 1: Four rectangles with dimensions $8 \times 3$, $8 \times 5$, $10 \times 20$ and $12 \times 15$ lead to an optimal answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Base on the fairy tale [Diamonds and Toads](https://en.wikipedia.org/wiki/Diamonds_and_Toads) from Charles Perrault. In this kata you will have to complete a function that take 2 arguments: 

- A string, that correspond to what the daugther says.
- A string, that tell you wich fairy the girl have met, this one can be `good` or `evil`. 

The function should return the following count as a hash:

- If the girl have met the `good` fairy:
  - count 1 `ruby` everytime you see a `r` and 2 everytime you see a `R`
  - count 1 `crystal` everytime you see a `c` and 2 everytime you see a `C`
- If the girl have met the `evil` fairy: 
  - count 1 `python` everytime you see a `p` and 2 everytime uou see a `P`
  - count 1 `squirrel` everytime you see a `s` and 2 everytime you see a `S`
  
**Note**: For this kata I decided to remplace the normal `Diamonds` and `Toads` by some programming languages. And just discover that [Squirrel](https://en.wikipedia.org/wiki/Squirrel_(programming_language) is a programming language.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
~~~if-not:java
You have to code a function **getAllPrimeFactors** wich take an integer as parameter and return an array containing its prime decomposition by ascending factors, if a factors appears multiple time in the decomposition it should appear as many time in the array. 

exemple: `getAllPrimeFactors(100)` returns `[2,2,5,5]` in this order. 

This decomposition may not be the most practical. 

You should also write **getUniquePrimeFactorsWithCount**, a function which will return an array containing two arrays: one with prime numbers appearing in the decomposition and the other containing their respective power. 

exemple: `getUniquePrimeFactorsWithCount(100)` returns `[[2,5],[2,2]]`

You should also write **getUniquePrimeFactorsWithProducts** an array containing the prime factors to their respective powers. 

exemple: `getUniquePrimeFactorsWithProducts(100)` returns `[4,25]`
~~~
~~~if:java
You have to code a function **getAllPrimeFactors** wich take an integer as parameter and return an array containing its prime decomposition by ascending factors, if a factors appears multiple time in the decomposition it should appear as many time in the array. 

exemple: `getAllPrimeFactors(100)` returns `[2,2,5,5]` in this order. 

This decomposition may not be the most practical. 

You should also write **getUniquePrimeFactorsWithCount**, a function which will return an array containing two arrays: one with prime numbers appearing in the decomposition and the other containing their respective power. 

exemple: `getUniquePrimeFactorsWithCount(100)` returns `[[2,5],[2,2]]`

You should also write **getPrimeFactorPotencies** an array containing the prime factors to their respective powers. 

exemple: `getPrimeFactorPotencies(100)` returns `[4,25]`
~~~

Errors, if:

* `n` is not a number
* `n` not an integer 
* `n` is negative or 0 

The three functions should respectively return `[]`,  `[[],[]]` and `[]`. 

Edge cases: 

* if `n=0`, the function should respectively return `[]`, `[[],[]]` and  `[]`.
* if `n=1`, the function should respectively return `[1]`, `[[1],[1]]`, `[1]`.
* if `n=2`, the function should respectively return `[2]`, `[[2],[1]]`, `[2]`.

The result for `n=2` is normal. The result for `n=1` is arbitrary and has been chosen to return a usefull result. The result for `n=0` is also arbitrary 
but can not be chosen to be both usefull and intuitive. (`[[0],[0]]` would be meaningfull but wont work for general use of decomposition, `[[0],[1]]` would work but is not intuitive.)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a sequence of colorful stones. The color of each stone is one of red, green, or blue. You are given a string s. The i-th (1-based) character of s represents the color of the i-th stone. If the character is "R", "G", or "B", the color of the corresponding stone is red, green, or blue, respectively.

Initially Squirrel Liss is standing on the first stone. You perform instructions one or more times.

Each instruction is one of the three types: "RED", "GREEN", or "BLUE". After an instruction c, if Liss is standing on a stone whose colors is c, Liss will move one stone forward, else she will not move.

You are given a string t. The number of instructions is equal to the length of t, and the i-th character of t represents the i-th instruction.

Calculate the final position of Liss (the number of the stone she is going to stand on in the end) after performing all the instructions, and print its 1-based position. It is guaranteed that Liss don't move out of the sequence.


-----Input-----

The input contains two lines. The first line contains the string s (1 ≤ |s| ≤ 50). The second line contains the string t (1 ≤ |t| ≤ 50). The characters of each string will be one of "R", "G", or "B". It is guaranteed that Liss don't move out of the sequence.


-----Output-----

Print the final 1-based position of Liss in a single line.


-----Examples-----
Input
RGB
RRR

Output
2

Input
RRRBGBRBBB
BBBRR

Output
3

Input
BRRBGBRGRBGRGRRGGBGBGBRGBRGRGGGRBRRRBRBBBGRRRGGBBB
BBRBGGRGRGBBBRBGRBRBBBBRBRRRBGBBGBBRRBBGGRBRRBRGRB

Output
15

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S, find the longest palindromic substring in S. Substring of string S: S[ i . . . . j ] where 0 ≤ i ≤ j < len(S). Palindrome string: A string which reads the same backwards. More formally, S is palindrome if reverse(S) = S. Incase of conflict, return the substring which occurs first ( with the least starting index ).
Example 1:
Input:
S = "aaaabbaa"
Output:
aabbaa
Explanation:
The longest palindrome string present in
the given string is "aabbaa".
Your Task:  
You don't need to read input or print anything. Your task is to complete the function longestPalindrome() which takes string S as input parameters and returns longest pallindrome present in string.
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{4}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have a garden consisting entirely of grass and weeds. Your garden is described by an *n*<=×<=*m* grid, with rows numbered 1 to *n* from top to bottom, and columns 1 to *m* from left to right. Each cell is identified by a pair (*r*,<=*c*) which means that the cell is located at row *r* and column *c*. Each cell may contain either grass or weeds. For example, a 4<=×<=5 garden may look as follows (empty cells denote grass):

You have a land-mower with you to mow all the weeds. Initially, you are standing with your lawnmower at the top-left corner of the garden. That is, at cell (1,<=1). At any moment of time you are facing a certain direction — either left or right. And initially, you face right.

In one move you can do either one of these:

1) Move one cell in the direction that you are facing.
 -  if you are facing right: move from cell (*r*,<=*c*) to cell (*r*,<=*c*<=+<=1)    -  if you are facing left: move from cell (*r*,<=*c*) to cell (*r*,<=*c*<=-<=1)    -  if you were facing right previously, you will face left    -  if you were facing left previously, you will face right    
You are not allowed to leave the garden. Weeds will be mowed if you and your lawnmower are standing at the cell containing the weeds (your direction doesn't matter). This action isn't counted as a move.

What is the minimum number of moves required to mow all the weeds?

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=150) — the number of rows and columns respectively. Then follow *n* lines containing *m* characters each — the content of the grid. "G" means that this cell contains grass. "W" means that this cell contains weeds. 

It is guaranteed that the top-left corner of the grid will contain grass.

Output Specification:
Print a single number — the minimum number of moves required to mow all the weeds.

Demo Input:
['4 5\nGWGGW\nGGWGG\nGWGGG\nWGGGG\n', '3 3\nGWW\nWWW\nWWG\n', '1 1\nG\n']

Demo Output:
['11\n', '7\n', '0\n']

Note:
For the first example, this is the picture of the initial state of the grid:

A possible solution is by mowing the weeds as illustrated below:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As a programmer, you sometimes have to deal with some math and this is the time to do it. You are given a list of binary relations, equalities and inequalities, like a = b, a != d, b = c etc. Your task is to output YES if you can assign integers to input variables in such a way, that you can satisfy all equalities and inequalities. Otherwise you should output NO. 

Input format:

In the first line there is one integer T denoting the number of test cases. Description of T test cases follow. Each one have two integers N and K given in the first line denoting the number of variables and the number of relations between them for this test case. All variables are represented by integers in range [1, N]. K lines follow. Each of them is of the form "x1 R x2" where x1 and x2 are integers representing variables and R is either "=" or "!=" and denotes the kind of relation between these variables.

Output format:

Output exactly T lines. In i-th of them, output the answer to the i-th test case.

Constraints:

T ≤ 10
1 ≤ N, K ≤ 10^6

Sum of N in one test file does not exceed 10^6
Sum of K in one test file does not exceed 10^6

SAMPLE INPUT
2
2 2
1 = 2
1 != 2
3 2
1 = 2
2 != 3

SAMPLE OUTPUT
NO
YES

Explanation

There are 2 test cases. In the first one, you cannot fulfill all relations, because equality and inequality of two number cannot be both true. In the second one,  you can for example assign 10 to 1 and 2 and 20 to 3 in order to fulfill all relations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a weighted undirected graph consisting of n$n$ nodes and m$m$ edges. The nodes are numbered from 1$1$ to n$n$. The graph does not contain any multiple edges or self loops.
A walk W$W$ on the graph is a sequence of vertices (with repetitions of vertices and edges allowed) such that every adjacent pair of vertices in the sequence is an edge of the graph. We define the cost of a walk W$W$, Cost(W)$Cost(W)$, as the maximum over the weights of the edges along the walk. 
You will be given q$q$ queries. In each query, you will be given an integer X$X$.

You have to count the number of different walks W$W$ of length 4$4$ such that Cost(W)$Cost(W)$ = X$X$.

Two walks are considered different if they do not represent the same edge sequence.

-----Input:-----
- First line contains 2 integers : the number of nodes n$n$ and number of edges m$m$.
- Next m$m$ lines each describe u$u$, v$v$ and w$w$, describing an edge between u$u$ and v$v$ with weight w$w$.
- Next line contains q$q$, the number of queries.
- Next q$q$ lines each describe an integer X$X$ - the cost of the walk in the query.

-----Output:-----
For each query, output in a single line the number of different possible walks.

-----Constraints-----
- 1≤n≤100$1 \leq n \leq 100$
- 1≤m≤n(n−1)2$1 \leq m \leq \frac{n (n-1)}{2}$
- 1≤u,v≤n$1 \leq u, v \leq n$
- 1≤w≤100$1 \leq w \leq 100$
- 1≤q≤100$1 \leq q \leq 100$
- 1≤X≤100$1 \leq X \leq 100$

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

-----Sample Output:-----
2
10
36

-----EXPLANATION:-----
For X=2$X = 2$, all possible 10$10$ walks are listed below :
- 1 -> 2 -> 1 -> 2 -> 3
- 1 -> 2 -> 3 -> 2 -> 1
- 1 -> 2 -> 3 -> 2 -> 3
- 2 -> 1 -> 2 -> 3 -> 2
- 2 -> 3 -> 2 -> 1 -> 2
- 2 -> 3 -> 2 -> 3 -> 2
- 3 -> 2 -> 1 -> 2 -> 1
- 3 -> 2 -> 1 -> 2 -> 3
- 3 -> 2 -> 3 -> 2 -> 1
- 3 -> 2 -> 3 -> 2 -> 3

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