vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Alan decided to get in shape for the summer, so he created a precise workout plan to follow. His plan is to go to a different gym every day during the next N days and lift $X[i]$ grams on day $i$. In order to improve his workout performance at the gym, he can buy exactly one pre-workout drink at the gym he is currently in and it will improve his performance by $A$ grams permanently and immediately. In different gyms these pre-workout drinks can cost different amounts $C[i]$ because of the taste and the gym's location but its permanent workout gains are the same. Before the first day of starting his workout plan, Alan knows he can lift a maximum of $K$ grams. Help Alan spend a minimum total amount of money in order to reach his workout plan. If there is no way for him to complete his workout plan successfully output $-1$.


-----Input-----

The first one contains two integer numbers, integers $N$ $(1 \leq N \leq 10^5)$ and $K$ $(1 \leq K \leq 10^5)$ – representing number of days in the workout plan and how many grams he can lift before starting his workout plan respectively. The second line contains $N$ integer numbers $X[i]$ $(1 \leq X[i] \leq 10^9)$ separated by a single space representing how many grams Alan wants to lift on day $i$. The third line contains one integer number $A$ $(1 \leq A \leq 10^9)$ representing permanent performance gains from a single drink. The last line contains $N$ integer numbers $C[i]$ $(1 \leq C[i] \leq 10^9)$ , representing cost of performance booster drink in the gym he visits on day $i$.


-----Output-----

One integer number representing minimal money spent to finish his workout plan. If he cannot finish his workout plan, output -1.


-----Examples-----
Input
5 10000
10000 30000 30000 40000 20000
20000
5 2 8 3 6

Output
5

Input
5 10000
10000 40000 30000 30000 20000
10000
5 2 8 3 6

Output
-1



-----Note-----

First example: After buying drinks on days 2 and 4 Alan can finish his workout plan. Second example: Alan cannot lift 40000 grams on day 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese  and Russian. 
The Physics teacher in Tanu's class is teaching concepts of a bouncing ball. The rubber ball that she is using has the property that if the ball is dropped from height H then, it bounces back to maximum height H/F. So after first bounce it rises up to maximum height H/F, after second bounce to maximum height H/F^{2}, after third bounce to maximum height H/F^{3}, and so on.
The class has N children, and the teacher wants to select two children such that when the taller child drops the ball from his height, ball reaches a maximum height equal to the height of the shorter child after some (possibly zero) number of bounces. Note that zero bounces mean heights of the two children will be same. Given the heights of the children in the class Height[i], can you tell how many ways are there for the teacher to select two children for the demonstration? Note that when heights are same, the pair is only counted once (See first example for further clarification).

------ Input ------ 

First line contains T, number of testcases. Then 2*T lines follow, 2 per testcase.
First line of each testcase consists of two space-separated intergers N and F. Second line of each testcase contains N space-separated integers representing the array Height.

------ Output ------ 

For each testcase, print a single line containing the answer to the problem.

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

$For 40 points: 1 ≤ T ≤ 100, 1 ≤ N ≤ 10^{3}, 2 ≤ F ≤ 10^{9}, 1 ≤ Height[i] ≤ 10^{9}
$$For 60 points: 1 ≤ T ≤ 100, 1 ≤ N ≤ 10^{4}, 2 ≤ F ≤ 10^{9}, 1 ≤ Height[i] ≤ 10^{9}$

----- Sample Input 1 ------ 
2
3 2
2 2 2
3 2
2 1 4
----- Sample Output 1 ------ 
3
3
----- explanation 1 ------ 
In the first case, the three pairs are (child 1, child 2), (child 2, child 3) and (child 1, child 3).
For the second case also, the three pairs are (child 1, child 2), (child 2, child 3) and (child 1, child 3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Monocarp got a job. His working day lasts exactly m minutes. During work, Monocarp wants to drink coffee at certain moments: there are n minutes a_1, a_2, ..., a_n, when he is able and willing to take a coffee break (for the sake of simplicity let's consider that each coffee break lasts exactly one minute). 

However, Monocarp's boss doesn't like when Monocarp takes his coffee breaks too often. So for the given coffee break that is going to be on minute a_i, Monocarp must choose the day in which he will drink coffee during the said minute, so that every day at least d minutes pass between any two coffee breaks. Monocarp also wants to take these n coffee breaks in a minimum possible number of working days (he doesn't count days when he is not at work, and he doesn't take coffee breaks on such days). Take into account that more than d minutes pass between the end of any working day and the start of the following working day.

For each of the n given minutes determine the day, during which Monocarp should take a coffee break in this minute. You have to minimize the number of days spent. 

Input

The first line contains three integers n, m, d (1 ≤ n ≤ 2⋅10^{5}, n ≤ m ≤ 10^{9}, 1 ≤ d ≤ m) — the number of coffee breaks Monocarp wants to have, the length of each working day, and the minimum number of minutes between any two consecutive coffee breaks.

The second line contains n distinct integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ m), where a_i is some minute when Monocarp wants to have a coffee break.

Output

In the first line, write the minimum number of days required to make a coffee break in each of the n given minutes. 

In the second line, print n space separated integers. The i-th of integers should be the index of the day during which Monocarp should have a coffee break at minute a_i. Days are numbered from 1. If there are multiple optimal solutions, you may print any of them.

Examples

Input

4 5 3
3 5 1 2


Output

3
3 1 1 2 


Input

10 10 1
10 5 7 4 6 3 2 1 9 8


Output

2
2 1 1 2 2 1 2 1 1 2 

Note

In the first example, Monocarp can take two coffee breaks during the first day (during minutes 1 and 5, 3 minutes will pass between these breaks). One break during the second day (at minute 2), and one break during the third day (at minute 3).

In the second example, Monocarp can determine the day of the break as follows: if the minute when he wants to take a break is odd, then this break is on the first day, if it is even, then this break is on the second day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three strings A, B and C. Check whether they form a word chain.
More formally, determine whether both of the following are true:
 - The last character in A and the initial character in B are the same.
 - The last character in B and the initial character in C are the same.
If both are true, print YES. Otherwise, print NO.

-----Constraints-----
 - A, B and C are all composed of lowercase English letters (a - z).
 - 1 ≤ |A|, |B|, |C| ≤ 10, where |A|, |B| and |C| are the lengths of A, B and C, respectively.

-----Input-----
Input is given from Standard Input in the following format:
A B C

-----Output-----
Print YES or NO.

-----Sample Input-----
rng gorilla apple

-----Sample Output-----
YES

They form a word chain.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A rectangle with sides $A$ and $B$ is cut into rectangles with cuts parallel to its sides. For example, if $p$ horizontal and $q$ vertical cuts were made, $(p + 1) \cdot (q + 1)$ rectangles were left after the cutting. After the cutting, rectangles were of $n$ different types. Two rectangles are different if at least one side of one rectangle isn't equal to the corresponding side of the other. Note that the rectangle can't be rotated, this means that rectangles $a \times b$ and $b \times a$ are considered different if $a \neq b$.

For each type of rectangles, lengths of the sides of rectangles are given along with the amount of the rectangles of this type that were left after cutting the initial rectangle.

Calculate the amount of pairs $(A; B)$ such as the given rectangles could be created by cutting the rectangle with sides of lengths $A$ and $B$. Note that pairs $(A; B)$ and $(B; A)$ are considered different when $A \neq B$.


-----Input-----

The first line consists of a single integer $n$ ($1 \leq n \leq 2 \cdot 10^{5}$) — amount of different types of rectangles left after cutting the initial rectangle.

The next $n$ lines each consist of three integers $w_{i}, h_{i}, c_{i}$ $(1 \leq w_{i}, h_{i}, c_{i} \leq 10^{12})$ — the lengths of the sides of the rectangles of this type and the amount of the rectangles of this type.

It is guaranteed that the rectangles of the different types are different.


-----Output-----

Output one integer — the answer to the problem.


-----Examples-----
Input
1
1 1 9

Output
3

Input
2
2 3 20
2 4 40

Output
6

Input
2
1 2 5
2 3 5

Output
0



-----Note-----

In the first sample there are three suitable pairs: $(1; 9)$, $(3; 3)$ and $(9; 1)$.

In the second sample case there are 6 suitable pairs: $(2; 220)$, $(4; 110)$, $(8; 55)$, $(10; 44)$, $(20; 22)$ and $(40; 11)$.

Here the sample of cut for $(20; 22)$.

 [Image] 

The third sample has no suitable pairs.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s and an integer k.
Return the maximum number of vowel letters in any substring of s with length k.
Vowel letters in English are (a, e, i, o, u).
 
Example 1:
Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:
Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:
Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Example 4:
Input: s = "rhythms", k = 4
Output: 0
Explanation: We can see that s doesn't have any vowel letters.

Example 5:
Input: s = "tryhard", k = 4
Output: 1

 
Constraints:

1 <= s.length <= 10^5
s consists of lowercase English letters.
1 <= k <= s.length

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of n integers. For each element output the sum of itself and the previous element. For the first element, output the sum of the first and the last elements of the array.

Input

The input consists of a single line of space-separated integers. The first number is n (2 ≤ n ≤ 50) — the size of the array. The following n numbers are the elements of the array (1 ≤ ai ≤ 1000).

Output

Output the sums a1 + an, a2 + a1, ..., an + an - 1, separated with spaces.

Examples

Input

4 1 2 3 4


Output

5 3 5 7 

Input

5 5 46 372 81 9


Output

14 51 418 453 90 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A company makes triangle-shaped ornaments for the upcoming holidays. Each ornament is tied at one of its corners to a rod using a string of unknown length. Multiple of these ornaments may be attached to the same rod. These ornaments should be able to swing (rotate around the axis formed by the string) without interfering with each other. 

Write a program that computes the minimum required length for the rod, given a list of triangles!

-----Input-----
The input consists of a single test case. The first line contains one integer $N$ ($0 < N \le 100$), denoting the number of triangles. The next $N$ lines each contain three integers $A, B, C$ denoting the lengths of the three sides of each triangle. The triangle will hang from the corner between sides $A$ and $B$. You are guaranteed that $A, B, C$ form a triangle that has an area that is strictly greater than zero.

-----Output-----
Output the required length $L$ such that all triangles can be hung from the rod, no matter how long or short each triangle’s string is. No triangle should swing beyond the rod’s ends. You may ignore the thickness of each ornament, the width of the string and you may assume that the string is attached exactly to the triangle’s end point.

Your answer should be accurate to within an absolute or relative error of $10^{-4}$.

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

Sample Input 2:
2
3 3 3
4 5 4
Sample Output 2:
6.843530573929037

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
According to Wikipedia, to hear something “through the grapevine” is to learn of something informally and unofficially by means of gossip or rumor. In this problem, you are tasked with determining how many people will hear about a particular rumor “through the grapevine” after a certain number of days.

Rumors are always started by a single person. On any given day, a person who knows the rumor can spread it by telling the people that they know. Upon hearing of the rumor, that person must wait until the following day before they can begin to spread it themselves. Furthermore, some people are skeptical and will only spread the rumor once they’ve heard it from a number of distinct sources. However once a person has heard the rumor from enough people, they will always try to spread the rumor to as many people as possible.

-----Input-----
The first line will contain three integers: $0 < n \leq 100000$, $0 < m \leq 100000$, and $0 \leq d \leq 10000$, where $n$ is the number of people, $m$ is the number of connections, and $d$ is the number of days that elapse.

The next $n$ lines will each consist of a unique string $s$ and an integer $0 \leq t \leq 1000$ where $s$ is the name of a person and $t$ is their level of skepticism. In other words, person $s$ must hear the rumor from $t$ distinct other people before $s$ will begin spreading the rumor.

This is followed by $m$ lines each consisting of two strings $u$ and $v$ which indicates that person $u$ and person $v$ know each other. Each of these lines represents a unique pair of persons.

The final line will contain a single string $r$, the name of the person that the rumor originates from. Note that $r$ is the only person with skepticism $t = 0$. All strings are between $1$ and $20$ characters long and consists only of English lowercase or uppercase letters and digits.

-----Output-----
Output a single integer: the number of people (not including person $r$) that have heard the rumor after $d$ days.

-----Examples-----
Sample Input:
3 2 1
Alice 0
Bob 1
Carol 1
Alice Bob
Bob Carol
Alice
Sample Output:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monocarp has got an array $a$ consisting of $n$ integers. Let's denote $k$ as the mathematic mean of these elements (note that it's possible that $k$ is not an integer).

The mathematic mean of an array of $n$ elements is the sum of elements divided by the number of these elements (i. e. sum divided by $n$).

Monocarp wants to delete exactly two elements from $a$ so that the mathematic mean of the remaining $(n - 2)$ elements is still equal to $k$.

Your task is to calculate the number of pairs of positions $[i, j]$ ($i < j$) such that if the elements on these positions are deleted, the mathematic mean of $(n - 2)$ remaining elements is equal to $k$ (that is, it is equal to the mathematic mean of $n$ elements of the original array $a$).


-----Input-----

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

The first line of each testcase contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of elements in the array.

The second line contains a sequence of integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{9}$), where $a_i$ is the $i$-th element of the array.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print one integer — the number of pairs of positions $[i, j]$ ($i < j$) such that if the elements on these positions are deleted, the mathematic mean of $(n - 2)$ remaining elements is equal to $k$ (that is, it is equal to the mathematic mean of $n$ elements of the original array $a$).


-----Examples-----

Input
4
4
8 8 8 8
3
50 20 10
5
1 4 7 3 5
7
1 2 3 4 5 6 7
Output
6
0
2
3


-----Note-----

In the first example, any pair of elements can be removed since all of them are equal.

In the second example, there is no way to delete two elements so the mathematic mean doesn't change.

In the third example, it is possible to delete the elements on positions $1$ and $3$, or the elements on positions $4$ and $5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi had a pair of two positive integers not exceeding N, (a,b), which he has forgotten.
He remembers that the remainder of a divided by b was greater than or equal to K.
Find the number of possible pairs that he may have had.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - 0 \leq K \leq N-1
 - All input values are integers.

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

-----Output-----
Print the number of possible pairs that he may have had.

-----Sample Input-----
5 2

-----Sample Output-----
7

There are seven possible pairs: (2,3),(5,3),(2,4),(3,4),(2,5),(3,5) and (4,5).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One of the built-in functions of Python is divmod, which takes two arguments $\boldsymbol{\alpha}$ and $\boldsymbol{b}$ and returns a tuple containing the quotient of $a/b$ first and then the remainder $\boldsymbol{a}$.  

For example:  

>>> print divmod(177,10)
(17, 7)

Here, the integer division is 177/10 => 17 and the modulo operator is 177%10 => 7.

Task 

Read in two integers, $\boldsymbol{a}$ and $\boldsymbol{b}$, and print three lines. 

The first line is the integer division $\boldsymbol{a}//b$ (While using Python2 remember to import division from __future__). 

The second line is the result of the modulo operator: $a\%b$. 

The third line prints the divmod of $\boldsymbol{a}$ and $\boldsymbol{b}$.  

Input Format 

The first line contains the first integer, $\boldsymbol{a}$, and the second line contains the second integer, $\boldsymbol{b}$.   

Output Format 

Print the result as described above.  

Sample Input  

177
10

Sample Output  

17
7
(17, 7)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.
Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.




Example 2:

Input: [1,2,2,3,1,4,2]
Output: 6



Note:
nums.length will be between 1 and 50,000.
nums[i] will be an integer between 0 and 49,999.

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

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


> $N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$

Output

* You have to print $N$ lines.
* The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.



Constraints

* $3 \le N, Q \le 100,000$
* $1 \le a_i \le N$
* $1 \le b_i \le 10^{12}$
* Any final results do not exceed $2 \times 10^{13}$.



Subtasks

Subtask 1 [ $60$ points ]


* $N, Q \le 100$
* $b_i = 1$

Subtask 2 [ $400$ points ]


* $N, Q \le 100$
* $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]


* $N, Q \le 100,000$
* $b_i = 1$

Subtask 4 [ $500$ points ]


* There are no additional constraints.

Output

* You have to print $N$ lines.
* The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.



Constraints

* $3 \le N, Q \le 100,000$
* $1 \le a_i \le N$
* $1 \le b_i \le 10^{12}$
* Any final results do not exceed $2 \times 10^{13}$.



Subtasks

Subtask 1 [ $60$ points ]


* $N, Q \le 100$
* $b_i = 1$

Subtask 2 [ $400$ points ]


* $N, Q \le 100$
* $b_i \le 10^{12}$

Subtask 3 [ $240$ points ]


* $N, Q \le 100,000$
* $b_i = 1$

Subtask 4 [ $500$ points ]


* There are no additional constraints.

Input

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


> $N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$

Examples

Input

9 3
5 11
8 4
4 7


Output

4
4
4
4
2
2
1
1
0


Input

6 6
3 5
6 11
1 6
4 7
5 2
2 5


Output

10
10
5
5
4
2


Input

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


Output

2
2
1
1
0


Input

10 10
10 10
9 20
8 30
7 40
6 50
5 60
4 70
3 80
2 90
1 100


Output

223
123
77
50
33
21
12
7
3
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Have you ever wished to be given a direct problem statement in the contest? Do you hate the boring stories that problem setters write...starting from “john was going on a trip”…passing with “blablabla”…and ending with “kindly help John J”. We all know that there is no John so why wasting contestants time. As we were contestants and know that feeling very well, we decided to break that boring way and save your time…

So, here is the question

There are n elements in a set. Some elements might be related to 0 elements in the set , some might be related to 1 element in the set and so on...
What you need to do is remove all elements which are related to exactly 0 elements then remove all elements which are related to exactly 1 elements in the remaining set and repeat the process till n-1 elements. 

Note : 
1. If a is related to b, b is also related to a.
2. If A is related to only one element say B, and B has realation with A and C then while removing all elements which are related to exactly 1 elements A will be removed and after that B will have only one relation i.e with C, but you can't remove B then beause you will remove all elements which are realted to exactly 2 elements in your next iteration.

You need to print the maximum number of elements that can be left in the set after N-1 iterations.

Input 
N ( number of test cases) followed by N lines each line contains number of elements in a set

Output
N lines (maximum number of elements that can be left in the set.)

Constraints
0<N<100000
0<N<100000

SAMPLE INPUT
2
1
3

SAMPLE OUTPUT
0
1

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