vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a sequence of $n$ integers $a_1, a_2, \ldots, a_n$.

You have to construct two sequences of integers $b$ and $c$ with length $n$ that satisfy:  for every $i$ ($1\leq i\leq n$) $b_i+c_i=a_i$  $b$ is non-decreasing, which means that for every $1<i\leq n$, $b_i\geq b_{i-1}$ must hold  $c$ is non-increasing, which means that for every $1<i\leq n$, $c_i\leq c_{i-1}$ must hold 

You have to minimize $\max(b_i,c_i)$. In other words, you have to minimize the maximum number in sequences $b$ and $c$.

Also there will be $q$ changes, the $i$-th change is described by three integers $l,r,x$. You should add $x$ to $a_l,a_{l+1}, \ldots, a_r$. 

You have to find the minimum possible value of $\max(b_i,c_i)$ for the initial sequence and for sequence after each change.


-----Input-----

The first line contains an integer $n$ ($1\leq n\leq 10^5$).

The secound line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq i\leq n$, $-10^9\leq a_i\leq 10^9$).

The third line contains an integer $q$ ($1\leq q\leq 10^5$).

Each of the next $q$ lines contains three integers $l,r,x$ ($1\leq l\leq r\leq n,-10^9\leq x\leq 10^9$), desribing the next change. 


-----Output-----

Print $q+1$ lines.

On the $i$-th ($1 \leq i \leq q+1$) line, print the answer to the problem for the sequence after $i-1$ changes.


-----Examples-----
Input
4
2 -1 7 3
2
2 4 -3
3 4 2

Output
5
5
6

Input
6
-9 -10 -9 -6 -5 4
3
2 6 -9
1 2 -10
4 6 -3

Output
3
3
3
1

Input
1
0
2
1 1 -1
1 1 -1

Output
0
0
-1



-----Note-----

In the first test:  The initial sequence $a = (2, -1, 7, 3)$. Two sequences $b=(-3,-3,5,5),c=(5,2,2,-2)$ is a possible choice.  After the first change $a = (2, -4, 4, 0)$. Two sequences $b=(-3,-3,5,5),c=(5,-1,-1,-5)$ is a possible choice.  After the second change $a = (2, -4, 6, 2)$. Two sequences $b=(-4,-4,6,6),c=(6,0,0,-4)$ is a possible choice.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a string S of length N, consisting of +, -, and 0, where + denotes a source of positive charge, - denotes a source of negative charge, and 0 denotes a neutral object.

Each second, the charge sources emit their respective charge to their immediate neighbours. The charge emissions cannot affect other charge sources but can convert a neutral object into a charge source as following:
If an object was initially neutral, and had exactly one charged source as neighbour, it becomes a charged source as received by its neighbour.
If an object was initially neutral, and had no charged source as neighbour, it remains a neutral object.
If an object was initially neutral, and had both charged sources as neighbours, it becomes a charged source as received by its neighbours. Note that in case of neighbours with opposite charges, the object remains neutral.

For example, after one second, +0+ becomes +++, 00- becomes 0--, 000 remains 000 and +0- remains +0-. Refer to samples for further explanation.

Find out the number of neutral objects in the string after infinite time. 

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of objects.
- The next line contains a string S of length N, consisting of +, -, and 0, where + denotes a source of positive charge, - denotes a source of negative charge, and 0 denotes a neutral object.

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

For each test case, output on a new line, the number of neutral objects in the string after infinite time. 

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

$1 ≤ T ≤ 2000$
$1 ≤ N ≤ 10^{5}$
$S$ consists of +, -, and 0 only.
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
4
2
00
3
-+0
6
00+-00
8
0-0+000-

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

----- explanation 1 ------ 
Test case $1$: Since there is no charge source, both neutral objects will remain neutral.

Test case $2$: After $1$ second:
- The negative source emits a negative charge, but since there is no neutral neighbour for the negative source, it has no effect.
- The positive source emits a positive charge and since the neighbour to its right is neutral, the neutral object becomes a positive source.

Thus, the string becomes -++ after one second. Note that the string will remain the same after this and thus, it has no neutral objects after infinite time.

Test case $3$:
- After $1$ second, the string is 0++--0. Note that only the immediate neutral neighbours of charge sources have been affected.
- After $2$ seconds, the string is +++---. Since all objects are now charged sources, they will remain the same now onwards.

Thus, after infinite time, the string has no neutral objects.

Test case $4$: After $1$ second, the string is --0++0--. Note that the string will remain the same now onwards.

Thus, after infinite time, the string has $2$ neutral objects.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day, Twilight Sparkle is interested in how to sort a sequence of integers a_1, a_2, ..., a_{n} in non-decreasing order. Being a young unicorn, the only operation she can perform is a unit shift. That is, she can move the last element of the sequence to its beginning:a_1, a_2, ..., a_{n} → a_{n}, a_1, a_2, ..., a_{n} - 1. 

Help Twilight Sparkle to calculate: what is the minimum number of operations that she needs to sort the sequence?


-----Input-----

The first line contains an integer n (2 ≤ n ≤ 10^5). The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5).


-----Output-----

If it's impossible to sort the sequence output -1. Otherwise output the minimum number of operations Twilight Sparkle needs to sort it.


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

Output
1

Input
3
1 3 2

Output
-1

Input
2
1 2

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Compare two version numbers version1 and version2.
If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Example 1:


Input: version1 = "0.1", version2 = "1.1"
Output: -1

Example 2:


Input: version1 = "1.0.1", version2 = "1"
Output: 1

Example 3:


Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Apple considers any iPhone with a battery health of 80\% or above, to be in *optimal* condition. 

Given that your iPhone has X\% battery health, find whether it is in *optimal* condition.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains an integer X — the battery health.

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

For each test case, output on a new line, YES, if the battery is in *optimal* condition, and NO otherwise.

You may print each character in uppercase or lowercase. For example, NO, no, No and nO, are all considered identical.

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

$1 ≤ T ≤ 100$
$0 ≤ X ≤ 100$

----- Sample Input 1 ------ 
4
97
42
80
10

----- Sample Output 1 ------ 
YES
NO
YES
NO

----- explanation 1 ------ 
Test case $1$: The battery health is $97 \%$ which is greater than equal to $80 \%$. Thus, the battery is in optimal condition.

Test case $2$: The battery health is $42 \%$ which is less than $80 \%$. Thus, the battery is not in optimal condition.

Test case $3$: The battery health is $80 \%$ which is greater than equal to $80 \%$. Thus, the battery is in optimal condition.

Test case $4$: The battery health is $10 \%$ which is less than $80 \%$. Thus, the battery is not in optimal condition.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
George has won the lottery and, being a nice guy, has decided to spread the wealth around. However, monetary gifts can be taxed once they get over a certain size—the amount of tax depends on how much his friends have earned that year.

The amount of tax paid depends on tax bands. The bands start at zero. Each one takes a certain cut of income from the range of pre-tax income it covers. The final tax band applies to all income above its lower bound.

George is a savvy fellow and knows the number of tax bands, the amount of money each friend has earned and the amount he wants each friend to walk away with.

How much should George give to each friend before tax?

-----Input-----
 - One line containing an integer $B$ ($1 \le B \le 20$): the number of tax bands.
 - $B$ further lines, each containing two real numbers: $s_ i$ ($0 < s_ i \le 10^6$): the size in pounds of the $i^{th}$ tax band, and $p_ i$ ($0 \le p_ i \le 100$): the percentage taxation for that band.
 - One line containing a real number $P$ ($0 \le P \le 99.999$): the percentage tax on all income above other bands.
 - One line containing an integer $F$, ($0 < F \le 20$): the number of friends George wants to pay.
 - $F$ further lines, each containing two real numbers $e_ j$ and $m_ j$ ($0 \le e_ j \le 10^6$, $0 < m_ j \le 10^6$): the amount of money the $j^{th}$ friend has earned, and the amount of money they should receive after tax respectively.

Tax bands will be given in increasing order. All real numbers have at most $6$ decimals after the decimal point.

-----Output-----
 - $F$ lines, one for each friend specified in the input and in the same order.

Each line should contain one real number: the amount of money George will give to his friend, in order to arrive at the correct amount after they have paid tax.

All output must be accurate to an absolute or relative error of at most $10^{-6}$.

-----Examples-----
Sample Input:
1
1000 0
20
3
0.0 500
999.5 500
1000.0 500
Sample Output:
500.000000
624.875000
625.000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have three positive integers a, b and c. You don't know their values, but you know some information about them. Consider all three pairwise sums, i.e. the numbers a+b, a+c and b+c. You know exactly two (any) of three pairwise sums.

Your task is to find such three positive integers a, b and c which match the given information. It means that if you consider a+b, a+c and b+c, two out of all three of them are given in the input. Among all such triples, you must choose one with the minimum possible sum a+b+c, and among all triples with the minimum sum, you can print any.

You have to process q independent queries.

Input

The first line of the input contains one integer q (1 ≤ q ≤ 1000) — the number of queries.

The next q lines contain queries. Each query is given as two integers x and y (2 ≤ x, y ≤ 2 ⋅ 10^9), where x and y are any two out of the three numbers a+b, a+c and b+c.

Output

For each query print the answer to it: three positive integers a, b and c consistent with the given information. Among all such triples, you have to choose one with the minimum possible sum a+b+c. Among all triples with the minimum sum, you can print any.

Example

Input


3
123 13
2 2
2000000000 2000000000


Output


111 1 12
1 1 1
1999999999 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Bear and Fair Set

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Limak is a grizzly bear. He is big and dreadful. You were chilling in the forest when you suddenly met him. It's very unfortunate for you. He will eat all your cookies unless you can demonstrate your mathematical skills. To test you, Limak is going to give you a puzzle to solve.

It's a well-known fact that Limak, as every bear, owns a set of numbers. You know some information about the set:
 -  The elements of the set are distinct positive integers. -  The number of elements in the set is *n*. The number *n* is divisible by 5. -  All elements are between 1 and *b*, inclusive: bears don't know numbers greater than *b*. -  For each *r* in {0,<=1,<=2,<=3,<=4}, the set contains exactly  elements that give remainder *r* when divided by 5. (That is, there are  elements divisible by 5,  elements of the form 5*k*<=+<=1,  elements of the form 5*k*<=+<=2, and so on.) 
Limak smiles mysteriously and gives you *q* hints about his set. The *i*-th hint is the following sentence: "If you only look at elements that are between 1 and *upTo**i*, inclusive, you will find exactly *quantity**i* such elements in my set."

In a moment Limak will tell you the actual puzzle, but something doesn't seem right... That smile was very strange. You start to think about a possible reason. Maybe Limak cheated you? Or is he a fair grizzly bear?

Given *n*, *b*, *q* and hints, check whether Limak can be fair, i.e. there exists at least one set satisfying the given conditions. If it's possible then print ''fair". Otherwise, print ''unfair".

Input Specification:
The first line contains three integers *n*, *b* and *q* (5<=≤<=*n*<=≤<=*b*<=≤<=104, 1<=≤<=*q*<=≤<=104, *n* divisible by 5) — the size of the set, the upper limit for numbers in the set and the number of hints.

The next *q* lines describe the hints. The *i*-th of them contains two integers *upTo**i* and *quantity**i* (1<=≤<=*upTo**i*<=≤<=*b*, 0<=≤<=*quantity**i*<=≤<=*n*).

Output Specification:
Print ''fair" if there exists at least one set that has all the required properties and matches all the given hints. Otherwise, print ''unfair".

Demo Input:
['10 20 1\n10 10\n', '10 20 3\n15 10\n5 0\n10 5\n', '10 20 2\n15 3\n20 10\n']

Demo Output:
['fair\n', 'fair\n', 'unfair\n']

Note:
In the first example there is only one set satisfying all conditions: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

In the second example also there is only one set satisfying all conditions: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15}.

Easy to see that there is no set satisfying all conditions from the third example. So Limak lied to you :-(

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Polycarp and Div 3

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp likes numbers that are divisible by 3.

He has a huge number $s$. Polycarp wants to cut from it the maximum number of numbers that are divisible by $3$. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after $m$ such cuts, there will be $m+1$ parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by $3$.

For example, if the original number is $s=3121$, then Polycarp can cut it into three parts with two cuts: $3|1|21$. As a result, he will get two numbers that are divisible by $3$.

Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.

What is the maximum number of numbers divisible by $3$ that Polycarp can obtain?

Input Specification:
The first line of the input contains a positive integer $s$. The number of digits of the number $s$ is between $1$ and $2\cdot10^5$, inclusive. The first (leftmost) digit is not equal to 0.

Output Specification:
Print the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$.

Demo Input:
['3121\n', '6\n', '1000000000000000000000000000000000\n', '201920181\n']

Demo Output:
['2\n', '1\n', '33\n', '4\n']

Note:
In the first example, an example set of optimal cuts on the number is 3|1|21.

In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by $3$.

In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and $33$ digits 0. Each of the $33$ digits 0 forms a number that is divisible by $3$.

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers $0$, $9$, $201$ and $81$ are divisible by $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A n digit number has n*(n+1)/2 sub-numbers.  For example, all possible sub-numbers of 975 are 9 7 5 97 75 975. A number is called Lucky if all sub-numbers have different digit product.  Digit product of a number is product of its digits.   
For example, the number 23 is Lucky.  Sub-numbers of it are 2, 3 and 23 and digit products are 2, 3 and 6 respectively (All digit products are different). 975 is also lucky. Print 1 if given Number is Lucky else Print 0.
 
Example 1:
Input:
N = 324
Output:
1
Explanation:
All subsequences form different Digit
Products. So, Output is 1.
Example 2:
Input:
N = 323
Output:
0
Explanation:
Subsequences 32, and 23 form same
Digit Product, i.e, 6. So, Output is 0.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function isLuckyOrNot() which takes an Integer N as input and returns the answer.
 
Expected Time Complexity: O((Number of Digits)^{2})
Expected Auxiliary Space: O(Number of Digits)
 
Constraints:
1 <= N <= 10^{18}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Tree is a connected acyclic graph. Suppose you are given a tree consisting of *n* vertices. The vertex of this tree is called centroid if the size of each connected component that appears if this vertex is removed from the tree doesn't exceed .

You are given a tree of size *n* and can perform no more than one edge replacement. Edge replacement is the operation of removing one edge from the tree (without deleting incident vertices) and inserting one new edge (without adding new vertices) in such a way that the graph remains a tree. For each vertex you have to determine if it's possible to make it centroid by performing no more than one edge replacement.

Input Specification:
The first line of the input contains an integer *n* (2<=≤<=*n*<=≤<=400<=000) — the number of vertices in the tree. Each of the next *n*<=-<=1 lines contains a pair of vertex indices *u**i* and *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*) — endpoints of the corresponding edge.

Output Specification:
Print *n* integers. The *i*-th of them should be equal to 1 if the *i*-th vertex can be made centroid by replacing no more than one edge, and should be equal to 0 otherwise.

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

Demo Output:
['1 1 1 \n', '1 0 0 0 0 \n']

Note:
In the first sample each vertex can be made a centroid. For example, in order to turn vertex 1 to centroid one have to replace the edge (2, 3) with the edge (1, 3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.
Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.
 
Example 1:
Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13. 

Example 2:
Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

Example 3:
Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

 
Constraints:

1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2

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

Input

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


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Teja likes cricket very much and likes to watch it all the time, but he is bored of watching the
matches alone and asks his friend to give him company. But his friend doesn’t know how to read
cricket scores so Teja decided to teach him. To make him understand better Teja gave him a list of
scores of an innings of a match. The scores are ordered in the increasing order of time at which it
was recorded.

In the version of Cricket Teja follows, runs can't be taken away from the batting team and a batsmen is not allowed to bat once he is dismissed, also the innings gets over when the 10th wicket falls or when the required number of overs are completed and no more scores are recorded once an innings get over.

Now Teja wants his friend to find out if its a valid score card or not. Since his friend
is busy watching football he asks for your help to answer Teja.

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

- First line cointains an integer  N  denoting the number of scores recorded. 
- Next n line contain two integers Ri and Wi, Ri is the runs scored and Wi is the number of wickets
lost.

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

print “YES” if it is valid else print “NO” without quotes.

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

$1 ≤ N ≤ 10^{6}$
$0 ≤ Ri ≤ 10^{7}$
$0 ≤ Wi ≤ 10$

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

30 points : $1 ≤ N ≤ 10^{4}$
70 points : $Original  Constraints$

----- Sample Input 1 ------ 
3
1 1
4 1
7 6
----- Sample Output 1 ------ 
YES
----- explanation 1 ------ 

----- Sample Input 2 ------ 
3
1 1
9 1
7 6
----- Sample Output 2 ------ 
NO
----- explanation 2 ------

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