vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
We have a secret array. You don't know this array and you have to restore it. However, you know some facts about this array:

  The array consists of $n$ distinct positive (greater than $0$) integers.  The array contains two elements $x$ and $y$ (these elements are known for you) such that $x < y$.  If you sort the array in increasing order (such that $a_1 < a_2 < \ldots < a_n$), differences between all adjacent (consecutive) elements are equal (i.e. $a_2 - a_1 = a_3 - a_2 = \ldots = a_n - a_{n-1})$. 

It can be proven that such an array always exists under the constraints given below.

Among all possible arrays that satisfy the given conditions, we ask you to restore one which has the minimum possible maximum element. In other words, you have to minimize $\max(a_1, a_2, \dots, a_n)$.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains three integers $n$, $x$ and $y$ ($2 \le n \le 50$; $1 \le x < y \le 50$) — the length of the array and two elements that are present in the array, respectively.


-----Output-----

For each test case, print the answer: $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of the required array. If there are several answers, you can print any (it also means that the order of elements doesn't matter).

It can be proven that such an array always exists under the given constraints.


-----Example-----
Input
5
2 1 49
5 20 50
6 20 50
5 3 8
9 13 22

Output
1 49 
20 40 30 50 10
26 32 20 38 44 50 
8 23 18 13 3 
1 10 13 4 19 22 25 16 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex 1, every vertex and every edge of which has a number written on.

The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex v sad if there is a vertex u in subtree of vertex v such that dist(v, u) > a_{u}, where a_{u} is the number written on vertex u, dist(v, u) is the sum of the numbers written on the edges on the path from v to u.

Leaves of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a leaf if and only if the tree consists of a single vertex — root.

Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?


-----Input-----

In the first line of the input integer n (1 ≤ n ≤ 10^5) is given — the number of vertices in the tree.

In the second line the sequence of n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) is given, where a_{i} is the number written on vertex i.

The next n - 1 lines describe tree edges: i^{th} of them consists of two integers p_{i} and c_{i} (1 ≤ p_{i} ≤ n,  - 10^9 ≤ c_{i} ≤ 10^9), meaning that there is an edge connecting vertices i + 1 and p_{i} with number c_{i} written on it.


-----Output-----

Print the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.


-----Example-----
Input
9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8

Output
5



-----Note-----

The following image represents possible process of removing leaves from the tree:  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yraglac is running a daycare service for dogs. He has $N$ dogs and he would like to take them on a walk. However, before he can walk the dogs, he needs to feed them first.

Yraglac has $M$ feeding bowls. Because the dogs are very well trained, he can instruct a dog to eat from a specific bowl, but he can’t instruct multiple dogs to eat from the same bowl. A dog is considered to be fed after eating from a single bowl. However, different dogs may have different food preferences, so they may eat from the same food bowl at different speeds.

As you know, dogs get impatient if they have to wait for long periods of time. Therefore, Yraglac wants to minimize the total amount of time that dogs spend waiting. More formally, suppose $t$ is the longest amount of time in seconds that any dog spent eating. Yraglac wants to minimize $T=\sum _{i=1}^{N} t-t_ i$, where $t_ i$ is the time in seconds that the $i^\textrm {th}$ dog spends eating.

-----Input-----
The first line contains integers $N$ and $M$, where $2\leq N\leq M\leq 50$.

Each of the next $N$ lines of the input contains $M$ integers each. The $j^\textrm {th}$ integers on the $i^\textrm {th}$ line denotes the $t_{ij}$, the amount of time that the $i^\textrm {th}$ dog will spend on eating food from the $j^\textrm {th}$ bowl. Note that $1\leq t_{ij}\leq 200$.

-----Output-----
Output $T$, the minimum total waiting time in seconds.

-----Examples-----
Sample Input:
2 3
2 100 10
100 1 10
Sample Output:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given P, a permutation of (1,\ 2,\ ...\ N).

A string S of length N consisting of `0` and `1` is a good string when it meets the following criterion:

* The sequences X and Y are constructed as follows:
* First, let X and Y be empty sequences.
* For each i=1,\ 2,\ ...\ N, in this order, append P_i to the end of X if S_i= `0`, and append it to the end of Y if S_i= `1`.
* If X and Y have the same number of high elements, S is a good string. Here, the i-th element of a sequence is called high when that element is the largest among the elements from the 1-st to i-th element in the sequence.



Determine if there exists a good string. If it exists, find the lexicographically smallest such string.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 1 \leq P_i \leq N
* P_1,\ P_2,\ ...\ P_N are all distinct.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
P_1 P_2 ... P_N


Output

If a good string does not exist, print `-1`. If it exists, print the lexicographically smallest such string.

Examples

Input

6
3 1 4 6 2 5


Output

001001


Input

5
1 2 3 4 5


Output

-1


Input

7
1 3 2 5 6 4 7


Output

0001101


Input

30
1 2 6 3 5 7 9 8 11 12 10 13 16 23 15 18 14 24 22 26 19 21 28 17 4 27 29 25 20 30


Output

000000000001100101010010011101

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got string *s*, consisting of small English letters. Some of the English letters are good, the rest are bad.

A substring *s*[*l*...*r*] (1<=≤<=*l*<=≤<=*r*<=≤<=|*s*|) of string *s*<=<==<=<=*s*1*s*2...*s*|*s*| (where |*s*| is the length of string *s*) is string <=*s**l**s**l*<=+<=1...*s**r*.

The substring *s*[*l*...*r*] is good, if among the letters <=*s**l*,<=*s**l*<=+<=1,<=...,<=*s**r* there are at most *k* bad ones (look at the sample's explanation to understand it more clear).

Your task is to find the number of distinct good substrings of the given string *s*. Two substrings *s*[*x*...*y*] and *s*[*p*...*q*] are considered distinct if their content is different, i.e. *s*[*x*...*y*]<=≠<=*s*[*p*...*q*].

Input Specification:
The first line of the input is the non-empty string *s*, consisting of small English letters, the string's length is at most 1500 characters.

The second line of the input is the string of characters "0" and "1", the length is exactly 26 characters. If the *i*-th character of this string equals "1", then the *i*-th English letter is good, otherwise it's bad. That is, the first character of this string corresponds to letter "a", the second one corresponds to letter "b" and so on.

The third line of the input consists a single integer *k* (0<=≤<=*k*<=≤<=|*s*|) — the maximum acceptable number of bad characters in a good substring.

Output Specification:
Print a single integer — the number of distinct good substrings of string *s*.

Demo Input:
['ababab\n01000000000000000000000000\n1\n', 'acbacbacaa\n00000000000000000000000000\n2\n']

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

Note:
In the first example there are following good substrings: "a", "ab", "b", "ba", "bab".

In the second example there are following good substrings: "a", "aa", "ac", "b", "ba", "c", "ca", "cb".

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kris works in a large company "Blake Technologies". As a best engineer of the company he was assigned a task to develop a printer that will be able to print horizontal and vertical strips. First prototype is already built and Kris wants to tests it. He wants you to implement the program that checks the result of the printing.

Printer works with a rectangular sheet of paper of size *n*<=×<=*m*. Consider the list as a table consisting of *n* rows and *m* columns. Rows are numbered from top to bottom with integers from 1 to *n*, while columns are numbered from left to right with integers from 1 to *m*. Initially, all cells are painted in color 0.

Your program has to support two operations: 
 1.  Paint all cells in row *r**i* in color *a**i*; 1.  Paint all cells in column *c**i* in color *a**i*. 
If during some operation *i* there is a cell that have already been painted, the color of this cell also changes to *a**i*.

Your program has to print the resulting table after *k* operation.

Input Specification:
The first line of the input contains three integers *n*, *m* and *k* (1<=<=≤<=<=*n*,<=<=*m*<=<=≤<=5000, *n*·*m*<=≤<=100<=000, 1<=≤<=*k*<=≤<=100<=000) — the dimensions of the sheet and the number of operations, respectively.

Each of the next *k* lines contains the description of exactly one query: 
 -  1 *r**i* *a**i* (1<=≤<=*r**i*<=≤<=*n*, 1<=≤<=*a**i*<=≤<=109), means that row *r**i* is painted in color *a**i*; -  2 *c**i* *a**i* (1<=≤<=*c**i*<=≤<=*m*, 1<=≤<=*a**i*<=≤<=109), means that column *c**i* is painted in color *a**i*.

Output Specification:
Print *n* lines containing *m* integers each — the resulting table after all operations are applied.

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

Demo Output:
['3 1 3 \n2 2 2 \n0 1 0 \n', '1 1 1 \n1 0 1 \n1 1 1 \n1 0 1 \n1 1 1 \n']

Note:
The figure below shows all three operations for the first sample step by step. The cells that were painted on the corresponding step are marked gray.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arkady plays Gardenscapes a lot. Arkady wants to build two new fountains. There are n available fountains, for each fountain its beauty and cost are known. There are two types of money in the game: coins and diamonds, so each fountain cost can be either in coins or diamonds. No money changes between the types are allowed.

Help Arkady to find two fountains with maximum total beauty so that he can buy both at the same time.


-----Input-----

The first line contains three integers n, c and d (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) — the number of fountains, the number of coins and diamonds Arkady has.

The next n lines describe fountains. Each of these lines contain two integers b_{i} and p_{i} (1 ≤ b_{i}, p_{i} ≤ 100 000) — the beauty and the cost of the i-th fountain, and then a letter "C" or "D", describing in which type of money is the cost of fountain i: in coins or in diamonds, respectively.


-----Output-----

Print the maximum total beauty of exactly two fountains Arkady can build. If he can't build two fountains, print 0.


-----Examples-----
Input
3 7 6
10 8 C
4 3 C
5 6 D

Output
9

Input
2 4 5
2 5 C
2 1 D

Output
0

Input
3 10 10
5 5 C
5 5 C
10 11 D

Output
10



-----Note-----

In the first example Arkady should build the second fountain with beauty 4, which costs 3 coins. The first fountain he can't build because he don't have enough coins. Also Arkady should build the third fountain with beauty 5 which costs 6 diamonds. Thus the total beauty of built fountains is 9.

In the second example there are two fountains, but Arkady can't build both of them, because he needs 5 coins for the first fountain, and Arkady has only 4 coins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr[] of distinct integers of size N and a value sum, the task is to find the count of triplets (i, j, k), having (i<j<k) with the sum of (arr[i] + arr[j] + arr[k]) smaller than the given value sum.
Example 1:
Input: N = 4, sum = 2
arr[] = {-2, 0, 1, 3}
Output:  2
Explanation: Below are triplets with 
sum less than 2 (-2, 0, 1) and (-2, 0, 3). 
 
Example 2:
Input: N = 5, sum = 12
arr[] = {5, 1, 3, 4, 7}
Output: 4
Explanation: Below are triplets with 
sum less than 12 (1, 3, 4), (1, 3, 5), 
(1, 3, 7) and (1, 4, 5).
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function countTriplets() that take array arr[], integer N  and integer sum as parameters and returns the count of triplets.
Expected Time Complexity: O(N^{2}).
Expected Auxiliary Space: O(1).
Constraints:
3 ≤ N ≤ 10^{3}
-10^{3} ≤ arr[i] ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given few numbers, you need to print out the digits that are not being used.

Example:

```python
unused_digits(12, 34, 56, 78) # "09"
unused_digits(2015, 8, 26) # "3479"
```

Note:

- Result string should be sorted
- The test case won't pass Integer with leading zero

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Gosha is hunting. His goal is to catch as many Pokemons as possible. Gosha has *a* Poke Balls and *b* Ultra Balls. There are *n* Pokemons. They are numbered 1 through *n*. Gosha knows that if he throws a Poke Ball at the *i*-th Pokemon he catches it with probability *p**i*. If he throws an Ultra Ball at the *i*-th Pokemon he catches it with probability *u**i*. He can throw at most one Ball of each type at any Pokemon.

The hunting proceeds as follows: at first, Gosha chooses no more than *a* Pokemons at which he will throw Poke Balls and no more than *b* Pokemons at which he will throw Ultra Balls. After that, he throws the chosen Balls at the chosen Pokemons. If he throws both Ultra Ball and Poke Ball at some Pokemon, he is caught if and only if he is caught by any of these Balls. The outcome of a throw doesn't depend on the other throws.

Gosha would like to know what is the expected number of the Pokemons he catches if he acts in an optimal way. In other words, he would like to know the maximum possible expected number of Pokemons can catch.

Input Specification:
The first line contains three integers *n*, *a* and *b* (2<=≤<=*n*<=≤<=2000, 0<=≤<=*a*,<=*b*<=≤<=*n*) — the number of Pokemons, the number of Poke Balls and the number of Ultra Balls.

The second line contains *n* real values *p*1,<=*p*2,<=...,<=*p**n* (0<=≤<=*p**i*<=≤<=1), where *p**i* is the probability of catching the *i*-th Pokemon if Gosha throws a Poke Ball to it.

The third line contains *n* real values *u*1,<=*u*2,<=...,<=*u**n* (0<=≤<=*u**i*<=≤<=1), where *u**i* is the probability of catching the *i*-th Pokemon if Gosha throws an Ultra Ball to it.

All the probabilities are given with exactly three digits after the decimal separator.

Output Specification:
Print the maximum possible expected number of Pokemons Gosha can catch. The answer is considered correct if it's absolute or relative error doesn't exceed 10<=-<=4.

Demo Input:
['3 2 2\n1.000 0.000 0.500\n0.000 1.000 0.500\n', '4 1 3\n0.100 0.500 0.500 0.600\n0.100 0.500 0.900 0.400\n', '3 2 0\n0.412 0.198 0.599\n0.612 0.987 0.443\n']

Demo Output:
['2.75\n', '2.16\n', '1.011']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a list/array which contains only integers (positive and negative). Your job is to sum only the numbers that are the same and consecutive. The result should be one list.

Extra credit if you solve it in one line. You can assume there is never an empty list/array and there will always be an integer. 

Same meaning: 1 == 1

1 != -1

#Examples:

```
[1,4,4,4,0,4,3,3,1] # should return [1,12,0,4,6,1]

"""So as you can see sum of consecutives 1 is 1 
sum of 3 consecutives 4 is 12 
sum of 0... and sum of 2 
consecutives 3 is 6 ..."""

[1,1,7,7,3] # should return [2,14,3]
[-5,-5,7,7,12,0] # should return [-10,14,12,0]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kuro and Shiro are playing with a board composed of n squares lining up in a row.
The squares are numbered 1 to n from left to right, and Square s has a mark on it.
First, for each square, Kuro paints it black or white with equal probability, independently from other squares. Then, he puts on Square s a stone of the same color as the square.
Kuro and Shiro will play a game using this board and infinitely many black stones and white stones. In this game, Kuro and Shiro alternately put a stone as follows, with Kuro going first:
 - Choose an empty square adjacent to a square with a stone on it. Let us say Square i is chosen.
 - Put on Square i a stone of the same color as the square.
 - If there are squares other than Square i that contain a stone of the same color as the stone just placed, among such squares, let Square j be the one nearest to Square i. Change the color of every stone between Square i and Square j to the color of Square i.
The game ends when the board has no empty square.
Kuro plays optimally to maximize the number of black stones at the end of the game, while Shiro plays optimally to maximize the number of white stones at the end of the game.
For each of the cases s=1,\dots,n, find the expected value, modulo 998244353, of the number of black stones at the end of the game.

-----Notes-----
When the expected value in question is represented as an irreducible fraction p/q, there uniquely exists an integer r such that rq=p ~(\text{mod } 998244353) and 0 \leq r \lt 998244353, which we ask you to find.

-----Constraints-----
 - 1 \leq n \leq 2\times 10^5

-----Input-----
Input is given from Standard Input in the following format:
n

-----Output-----
Print n values.
The i-th value should be the expected value, modulo 998244353, of the number of black stones at the end of the game for the case s=i.

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

-----Sample Output-----
499122178
499122178
499122178

Let us use b to represent a black square and w to represent a white square.
There are eight possible boards: www, wwb, wbw, wbb, bww, bwb, bbw, and bbb, which are chosen with equal probability.
For each of these boards, there will be 0, 1, 0, 2, 1, 3, 2, and 3 black stones at the end of the game, respectively, regardless of the value of s.
Thus, the expected number of stones is (0+1+0+2+1+3+2+3)/8 = 3/2, and the answer is r = 499122178, which satisfies 2r = 3 ~(\text{mod } 998244353) and 0 \leq r \lt 998244353.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Numbers $1, 2, 3, \dots n$ (each integer from $1$ to $n$ once) are written on a board. In one operation you can erase any two numbers $a$ and $b$ from the board and write one integer $\frac{a + b}{2}$ rounded up instead.

You should perform the given operation $n - 1$ times and make the resulting number that will be left on the board as small as possible. 

For example, if $n = 4$, the following course of action is optimal:  choose $a = 4$ and $b = 2$, so the new number is $3$, and the whiteboard contains $[1, 3, 3]$;  choose $a = 3$ and $b = 3$, so the new number is $3$, and the whiteboard contains $[1, 3]$;  choose $a = 1$ and $b = 3$, so the new number is $2$, and the whiteboard contains $[2]$. 

It's easy to see that after $n - 1$ operations, there will be left only one number. Your goal is to minimize it.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The only line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of integers written on the board initially.

It's guaranteed that the total sum of $n$ over test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, in the first line, print the minimum possible number left on the board after $n - 1$ operations. Each of the next $n - 1$ lines should contain two integers — numbers $a$ and $b$ chosen and erased in each operation.


-----Example-----
Input
1
4

Output
2
2 4
3 3
3 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A sequence X_1, X_2, ..., X_n is fibonacci-like if:

n >= 3
X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A.  If one does not exist, return 0.
(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements.  For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)
 


Example 1:
Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:
Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].

 
Note:

3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
(The time limit has been reduced by 50% for submissions in Java, C, and C++.)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For her next karate demonstration, Ada will break some bricks.
Ada stacked three bricks on top of each other. Initially, their widths (from top to bottom) are W1,W2,W3.
Ada's strength is S. Whenever she hits a stack of bricks, consider the largest k≥0 such that the sum of widths of the topmost k bricks does not exceed S; the topmost k bricks break and are removed from the stack. Before each hit, Ada may also decide to reverse the current stack of bricks, with no cost.
Find the minimum number of hits Ada needs in order to break all bricks if she performs the reversals optimally. You are not required to minimise the number of reversals.
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 four space-separated integers S, W1, W2 and W3.Output
For each test case, print a single line containing one integer ― the minimum required number of hits.Constraints
- 1≤T≤64
- 1≤S≤8
- 1≤Wi≤2 for each valid i
it is guaranteed that Ada can break all bricksExample Input

3

3 1 2 2

2 1 1 1

3 2 2 1
Example Output

2

2

2
Explanation

Example case 1:

Ada can reverse the stack and then hit it two times. Before the first hit, the widths of bricks in the stack (from top to bottom) are (2,2,1). After the first hit, the topmost brick breaks and the stack becomes (2,1). The second hit breaks both remaining bricks.

In this particular case, it is also possible to hit the stack two times without reversing. Before the first hit, it is (1,2,2). The first hit breaks the two bricks at the top (so the stack becomes (2)) and the second hit breaks the last brick.

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