vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: New Year Transportation

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
New Year is coming in Line World! In this world, there are *n* cells numbered by integers from 1 to *n*, as a 1<=×<=*n* board. People live in cells. However, it was hard to move between distinct cells, because of the difficulty of escaping the cell. People wanted to meet people who live in other cells.

So, user tncks0121 has made a transportation system to move between these cells, to celebrate the New Year. First, he thought of *n*<=-<=1 positive integers *a*1,<=*a*2,<=...,<=*a**n*<=-<=1. For every integer *i* where 1<=≤<=*i*<=≤<=*n*<=-<=1 the condition 1<=≤<=*a**i*<=≤<=*n*<=-<=*i* holds. Next, he made *n*<=-<=1 portals, numbered by integers from 1 to *n*<=-<=1. The *i*-th (1<=≤<=*i*<=≤<=*n*<=-<=1) portal connects cell *i* and cell (*i*<=+<=*a**i*), and one can travel from cell *i* to cell (*i*<=+<=*a**i*) using the *i*-th portal. Unfortunately, one cannot use the portal backwards, which means one cannot move from cell (*i*<=+<=*a**i*) to cell *i* using the *i*-th portal. It is easy to see that because of condition 1<=≤<=*a**i*<=≤<=*n*<=-<=*i* one can't leave the Line World using portals.

Currently, I am standing at cell 1, and I want to go to cell *t*. However, I don't know whether it is possible to go there. Please determine whether I can go to cell *t* by only using the construted transportation system.

Input Specification:
The first line contains two space-separated integers *n* (3<=≤<=*n*<=≤<=3<=×<=104) and *t* (2<=≤<=*t*<=≤<=*n*) — the number of cells, and the index of the cell which I want to go to.

The second line contains *n*<=-<=1 space-separated integers *a*1,<=*a*2,<=...,<=*a**n*<=-<=1 (1<=≤<=*a**i*<=≤<=*n*<=-<=*i*). It is guaranteed, that using the given transportation system, one cannot leave the Line World.

Output Specification:
If I can go to cell *t* using the transportation system, print "YES". Otherwise, print "NO".

Demo Input:
['8 4\n1 2 1 2 1 2 1\n', '8 5\n1 2 1 2 1 1 1\n']

Demo Output:
['YES\n', 'NO\n']

Note:
In the first sample, the visited cells are: 1, 2, 4; so we can successfully visit the cell 4.

In the second sample, the possible cells to visit are: 1, 2, 4, 6, 7, 8; so we can't visit the cell 5, which we want to visit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have recently discovered that horses travel in a unique pattern - they're either running (at top speed) or resting (standing still).

Here's an example of how one particular horse might travel:

```
The horse Blaze can run at 14 metres/second for 60 seconds, but must then rest for 45 seconds.

After 500 seconds Blaze will have traveled 4200 metres.
```

Your job is to write a function that returns how long a horse will have traveled after a given time.

####Input: 

* totalTime - How long the horse will be traveling (in seconds)

* runTime - How long the horse can run for before having to rest (in seconds)

* restTime - How long the horse have to rest for after running (in seconds)

* speed - The max speed of the horse (in metres/second)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is the World Cup Finals. Chef only finds a match interesting if the skill difference of the competing teams is *less than or equal to* D.

Given that the skills of the teams competing in the final are X and Y respectively, determine whether Chef will find the game interesting or not. 

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

- The first line of input will contain a single integer T, denoting the number of testcases. The description of T testcases follows.
- Each testcase consists of a single line of input containing three space-separated integers X, Y, and D — the skill levels of the teams and the maximum skill difference.

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

For each testcase, output "YES" if Chef will find the game interesting, else output "NO" (without the quotes). The checker is case-insensitive, so "YeS" and "nO" etc. are also acceptable. 

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

$1 ≤ T ≤ 2000$
$1 ≤ X, Y ≤ 100$
$0 ≤ D ≤ 100$ 

----- Sample Input 1 ------ 
3
5 3 4
5 3 1
5 5 0

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

----- explanation 1 ------ 
Test case $1$: The skill difference between the teams is $2$, which is less than the maximum allowed difference of $4$.

Test case $2$: The skill difference between the teams is $2$, which is more than the maximum allowed difference of $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There has been a Galaxy war started between  Deo system and Sprite system . Mountain named planet is leader from Deo system and want to distribute some special information to all countries(infinite in number) of each planet in Deo system. Deo system's planets have some special bond among themselves that is each country is connected to other countries on a planet which means there is source of communication between any two countries on every planet of Deo system. 

To defeat Sprite system in war, Deo system have some strategies. Now Mountain planet as a leader wants to distribute these strategies to all countries of each of M planets and each planet have their own unique way to communicate among their countries. Mountain planet have N packets of information (same information in all N packets) and wants to distribute all the packets of information among M planets. 

For small number of planets people on Mountain planet can easily find number of ways Mountain planet can distribute the information but for large number of planets it has been difficult for them, so they hire you to help them finding the answer. Answer can be large so output the answer by Taking modulo with K  which is square free number and maximum prime it can contain is less than 100.

INPUT:

1st first line contain test cases T. Each test contain N,M,K.

OUTPUT:

Find number of ways Mountain planet can distribute the information.

CONSTRAINTS:

1 ≤ T ≤ 10

1 ≤ N,M ≤ 10^12

1 ≤ K ≤ 10^9

SAMPLE INPUT
2
5 1 6
3 2 7

SAMPLE OUTPUT
1
2

Explanation

In test case 1:
There is only 1 way to distribute the information. As there is only 1 planet, so give all N packets to that planet.
In test case 2:
There are only 2 ways to distribute the information: 
(1 packet to one planet and 2 packets to another planet) or (2 packets to one planet and 1 packet to another planet).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A haiku is a Japanese form of poetry. It consists of three phrases of $5$, $7$ and $5$ syllables each.

Once a year, HiQ has a haiku contest, where employees submit their best poems. The poems are then judged based on a wide range of aspects, such as
 - creativity
 - simplicity
 - beauty
 - whether the poem is actually a haiku

This last point turned out to be quite a challenge for the judges (many problems arose when half the judges indexed syllables starting at $0$ and the other half at $1$).

Can you help the judges to determine whether a submitted poem is a haiku, given a set of syllables? Note that there may exist multiple decompositions of a single word in the poem into syllables. In this case, you should determine whether some decomposition is a haiku.

-----Input-----
The first line of input contains a single integer $1 \le S \le 100$, the number of syllables. The next line contains $S$ words separated by spaces (the syllables). Each syllable contains at most $7$ lowercase letters a-z.

Then, three lines containing the poem follow. Each line contains a (non-empty) list of words separated by spaces, representing a phrase. The words contain only lowercase letters a-z. The length of each line is at most $100$ characters (including spaces).

It is guaranteed that there exists at least one decomposition of the poem into the given syllables.

-----Output-----
Output “haiku” if the given poem is a haiku, and “come back next year” otherwise (without the quotes).

-----Explanation of Sample Input 1-----
One possible decomposition into a haiku is:

spe-lling ve-ry hard
ear-ly in mor-ning ti-red
i need cov-fe-fe


-----Explanation of Sample Input 3-----
No matter how the third line is decomposed, it contains $8$ syllables instead of $5$, so it can not be a haiku.

-----Examples-----
Sample Input 1:
20
va
fi
ve
mor
lling
spe
in
i
sh
ti
hard
cov
ear
fe
red
ja
ry
need
ly
ning
spelling very hard
early in morning tired
i need covfefe
Sample Output 1:
haiku

Sample Input 2:
22
q
c
da
plus
to
the
e
thee
un
late
ci
a
shall
by
com
i
ru
pare
temp
ble
hi
de
shall i compare thee
to a c plus plus template
undecidable
Sample Output 2:
haiku

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

Given the birthdates of two people, find the date when the younger one is exactly half the age of the other.

# Notes

* The dates are given in the format YYYY-MM-DD and are not sorted in any particular order
* Round **down** to the nearest day
* Return the result as a string, like the input dates

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are cubes of the same size and a simple robot named Masato. Initially, all cubes are on the floor. Masato can be instructed to pick up a cube and put it on another cube, to make piles of cubes. Each instruction is of the form `pick up cube A and put it on cube B (or on the floor).'

When he is to pick up a cube, he does so after taking off all the cubes on and above it in the same pile (if any) onto the floor. In contrast, when he is to put a cube on another, he puts the former on top of the pile including the latter without taking any cubes off.

When he is instructed to put a cube on another cube and both cubes are already in the same pile, there are two cases. If the former cube is stacked somewhere below the latter, he put off all the cube above it onto the floor. Afterwards he puts the former cube on the latter cube. If the former cube is stacked somewhere above the latter, he just ignores the instruction.

When he is instructed to put a cube on the floor, there are also two cases. If the cube is already on the floor (including the case that the cube is stacked in the bottom of some pile), he just ignores the instruction. Otherwise, he puts off all the cube on and up above the pile (if any) onto the floor before moving the cube onto the floor.

He also ignores the instruction when told to put a cube on top of itself (this is impossible).

Given the number of the cubes and a series of instructions, simulate actions of Masato and calculate the heights of piles when Masato has finished his job.



Input

The input consists of a series of data sets. One data set contains the number of cubes as its first line, and a series of instructions, each described in a separate line. The number of cubes does not exceed 100. Each instruction consists of two numbers; the former number indicates which cube to pick up, and the latter number indicates on which cube to put it. The end of the instructions is marked by two zeros.

The end of the input is marked by the line containing a single zero.

One data set has the following form:


m
I1 J1
I2 J2
...
In Jn
0 0


Each cube is identified by its number (1 through m). Ik indicates which cube to pick up and Jk indicates on which cube to put it. The latter may be zero, instructing to put the cube on the floor.

Output

Output the height of each pile (the number of cubes in the pile) in ascending order, separated by newlines. A single cube by itself also counts as "a pile." End of output for one data set should be marked by a line containing the character sequence `end' by itself.

Example

Input

3
1 3
2 0
0 0
4
4 1
3 1
1 2
0 0
5
2 1
3 1
4 1
3 2
1 1
0 0
0


Output

1
2
end
1
1
2
end
1
4
end

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a cubic die with 6 faces kept on an infinite plane. Each face has a distinct integer in the range [1,6] written on it, but the exact arrangement of the numbers on the faces of the die is unknown to Chef. Curiosity gets the better of Chef and he wants to find out o(1), o(2), ..., o(6), where o(i) is the number written opposite to the number i.

	Chef performs the following N-1 steps to learn the exact arrangement of the numbers on the die. In the i-th step, Chef pushes the die in some direction (there are 4 possible directions), and the die rolls 90o in this direction. The picture below demonstrates a die and the result that it produced after rolling in each of the 4 directions respectively. For this die, we have o(1)=4, o(2)=5, o(3)=6, o(4)=1, o(5)=2, o(6)=3.

	Chef records N numbers A1, A2, ..., AN, where Ai is the number written on the top of the die before the i-th step. However, the information on the direction in which he pushes the die each time are lost. Can you help him determine the arrangement of 1-6? You need to output o(1), o(2), ..., o(6). If there are multiple solutions, output any one of them.

-----
	Input-----
- The first line of input contains a single integer T, the number of test cases.
- Each test case consists of two lines.
- The first line contains an integer N, and the second line contains N space-separated integers A1, A2, ..., AN.

-----
	Output-----

	For each test case, output one line. If a possible solution exists, then output 6 space-separated integers o(1), o(2), ..., o(6); otherwise, output -1.

-----
	Constraints-----

- 1 ≤ T, N ≤ 500
- 1 ≤ Ai ≤ 6

	Subtask #1 (17 points):

- N ≤ 2

	Subtask #2 (83 points):

- original constraints

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

Output:
2 1 6 5 4 3
-1
4 5 6 1 2 3
-1

-----
	Explanation-----
Example case 1: See below.

Example case 2: You can prove that there's no solution.
Example case 3: The solution is not unique. 3 5 1 6 2 4 is another valid solution.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has a string S consisting of lowercase English letters.
Starting with this string, he will produce a new one in the procedure given as follows.
The procedure consists of Q operations. In Operation i (1 \leq i \leq Q), an integer T_i is provided, which means the following:
 - If T_i = 1: reverse the string S.
 - If T_i = 2: An integer F_i and a lowercase English letter C_i are additionally provided.
 - If F_i = 1 : Add C_i to the beginning of the string S.
 - If F_i = 2 : Add C_i to the end of the string S.
Help Takahashi by finding the final string that results from the procedure.

-----Constraints-----
 - 1 \leq |S| \leq 10^5
 - S consists of lowercase English letters.
 - 1 \leq Q \leq 2 \times 10^5
 - T_i = 1 or 2.
 - F_i = 1 or 2, if provided.
 - C_i is a lowercase English letter, if provided.

-----Input-----
Input is given from Standard Input in the following format:
S
Q
Query_1
:
Query_Q

In the 3-rd through the (Q+2)-th lines, Query_i is one of the following:
1

which means T_i = 1, and:
2 F_i C_i

which means T_i = 2.

-----Output-----
Print the resulting string.

-----Sample Input-----
a
4
2 1 p
1
2 2 c
1

-----Sample Output-----
cpa

There will be Q = 4 operations. Initially, S is a.
 - Operation 1: Add p at the beginning of S. S becomes pa.
 - Operation 2: Reverse S. S becomes ap.
 - Operation 3: Add c at the end of S. S becomes apc.
 - Operation 4: Reverse S. S becomes cpa.
Thus, the resulting string is cpa.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program which manipulates a sequence A = {a1, a2, . . . , an} with the following operations:

* add(s, t, x): add x to as, as+1, ..., at.
* getSum(s, t): report the sum of as, as+1, ..., at.



Note that the initial values of ai (i = 1, 2, . . . , n) are 0.

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 100000
* 1 ≤ s ≤ t ≤ n
* 0 ≤ x < 1000

Input


n q
query1
query2
:
queryq


In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:


0 s t x


or


1 s t


The first digit represents the type of the query. '0' denotes add(s, t, x) and '1' denotes getSum(s, t).

Output

For each getSum operation, print the sum;

Examples

Input

3 5
0 1 2 1
0 2 3 2
0 3 3 3
1 1 2
1 2 3


Output

4
8


Input

4 3
1 1 4
0 1 4 1
1 1 4


Output

0
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S consisting of the characters 0, 1 and 2. Your task is to find the length of the smallest substring of string S that contains all the three characters 0, 1 and 2. If no such substring exists, then return -1.
Example 1:
Input:
S = "01212"
Output:
3
Explanation:
The substring 012 is the smallest substring
that contains the characters 0, 1 and 2.
Example 2:
Input: 
S = "12121"
Output:
-1
Explanation: 
As the character 0 is not present in the
string S, therefor no substring containing
all the three characters 0, 1 and 2
exists. Hence, the answer is -1 in this case.
Your Task:
Complete the function smallestSubstring() which takes the string S as input, and returns the length of the smallest substring of string S that contains all the three characters 0, 1 and 2.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{5}
All the characters of String S lies in the set {'0', '1', '2'}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp is in really serious trouble — his house is on fire! It's time to save the most valuable items. Polycarp estimated that it would take *t**i* seconds to save *i*-th item. In addition, for each item, he estimated the value of *d**i* — the moment after which the item *i* will be completely burned and will no longer be valuable for him at all. In particular, if *t**i*<=≥<=*d**i*, then *i*-th item cannot be saved.

Given the values *p**i* for each of the items, find a set of items that Polycarp can save such that the total value of this items is maximum possible. Polycarp saves the items one after another. For example, if he takes item *a* first, and then item *b*, then the item *a* will be saved in *t**a* seconds, and the item *b* — in *t**a*<=+<=*t**b* seconds after fire started.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=100) — the number of items in Polycarp's house.

Each of the following *n* lines contains three integers *t**i*,<=*d**i*,<=*p**i* (1<=≤<=*t**i*<=≤<=20, 1<=≤<=*d**i*<=≤<=2<=000, 1<=≤<=*p**i*<=≤<=20) — the time needed to save the item *i*, the time after which the item *i* will burn completely and the value of item *i*.

Output Specification:
In the first line print the maximum possible total value of the set of saved items. In the second line print one integer *m* — the number of items in the desired set. In the third line print *m* distinct integers — numbers of the saved items in the order Polycarp saves them. Items are 1-indexed in the same order in which they appear in the input. If there are several answers, print any of them.

Demo Input:
['3\n3 7 4\n2 6 5\n3 7 6\n', '2\n5 6 1\n3 3 5\n']

Demo Output:
['11\n2\n2 3 \n', '1\n1\n1 \n']

Note:
In the first example Polycarp will have time to save any two items, but in order to maximize the total value of the saved items, he must save the second and the third item. For example, he can firstly save the third item in 3 seconds, and then save the second item in another 2 seconds. Thus, the total value of the saved items will be 6 + 5 = 11.

In the second example Polycarp can save only the first item, since even if he immediately starts saving the second item, he can save it in 3 seconds, but this item will already be completely burned by this time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Like any unknown mathematician, Yuri has favourite numbers: $A$, $B$, $C$, and $D$, where $A \leq B \leq C \leq D$. Yuri also likes triangles and once he thought: how many non-degenerate triangles with integer sides $x$, $y$, and $z$ exist, such that $A \leq x \leq B \leq y \leq C \leq z \leq D$ holds?

Yuri is preparing problems for a new contest now, so he is very busy. That's why he asked you to calculate the number of triangles with described property.

The triangle is called non-degenerate if and only if its vertices are not collinear.


-----Input-----

The first line contains four integers: $A$, $B$, $C$ and $D$ ($1 \leq A \leq B \leq C \leq D \leq 5 \cdot 10^5$) — Yuri's favourite numbers.


-----Output-----

Print the number of non-degenerate triangles with integer sides $x$, $y$, and $z$ such that the inequality $A \leq x \leq B \leq y \leq C \leq z \leq D$ holds.


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

Output
4

Input
1 2 2 5

Output
3

Input
500000 500000 500000 500000

Output
1



-----Note-----

In the first example Yuri can make up triangles with sides $(1, 3, 3)$, $(2, 2, 3)$, $(2, 3, 3)$ and $(2, 3, 4)$.

In the second example Yuri can make up triangles with sides $(1, 2, 2)$, $(2, 2, 2)$ and $(2, 2, 3)$.

In the third example Yuri can make up only one equilateral triangle with sides equal to $5 \cdot 10^5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Since ACTA has entered into force, Slavko has been spending his time offline, solving crosswords. Having solved almost all that he could get his hands on, he wants to make a few crosswords of his own. However, he is too sloppy for such fine work, so he has asked you to help him generate the crosswords.

You are given two words, $A$ and $B$. The word $A$ must be output horizontally, and the word $B$ vertically, so that the two words cross (i.e., share exactly one letter). The shared letter must be the first letter in $A$ that is also contained in $B$, more specifically the first occurrence of that letter in each word.

For example, given the words $A = \texttt{ABBA}$ and $B = \texttt{CCBB}$, you need to output $4$ lines as shown below:

.C..
.C..
ABBA
.B..


-----Input-----
The first and only line of input contains two words, $A$ and $B$, not more than $30$ characters long, separated by a single space. Both words will contain only uppercase English letters. There will be at least one letter contained in both words.

-----Output-----
Let $N$ be the length of word $A$, and $M$ the length of word $B$. The output must contain $M$ lines, each containing $N$ characters. The character grid must contain the two words crossed as described above. All other characters in the grid must be periods (the character “.”, without quotes), thus padding all lines to the length of $N$ characters.

-----Examples-----
Sample Input 1:
BANANA PIDZAMA
Sample Output 1:
.P....
.I....
.D....
.Z....
BANANA
.M....
.A....

Sample Input 2:
MAMA TATA
Sample Output 2:
.T..
MAMA
.T..
.A..

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
Get the digits sum of `n`th number from the [Look-and-Say sequence](http://en.wikipedia.org/wiki/Look-and-say_sequence)(1-based).

`1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ...`

# Input/Output

`[input]` integer `n`

`n`th number in the sequence to get where `1 <= n <= 55`  and `n=1 is "1"`.

[output] an integer

The sum of digits in `n`th number from the `Look-and-Say` sequence.

# Example

For `n = 2`, the output shoule be 2.

`"11" --> 1 + 1 --> 2`

For `n = 3`, the output shoule be 3.

`"21" --> 2 + 1 --> 3`

For `n = 4`, the output shoule be 5.

`"1211" --> 1 + 2 + 1 + 1 --> 5`

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