vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Shaass and Oskols

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Shaass has decided to hunt some birds. There are *n* horizontal electricity wires aligned parallel to each other. Wires are numbered 1 to *n* from top to bottom. On each wire there are some oskols sitting next to each other. Oskol is the name of a delicious kind of birds in Shaass's territory. Supposed there are *a**i* oskols sitting on the *i*-th wire.

Sometimes Shaass shots one of the birds and the bird dies (suppose that this bird sat at the *i*-th wire). Consequently all the birds on the *i*-th wire to the left of the dead bird get scared and jump up on the wire number *i*<=-<=1, if there exists no upper wire they fly away. Also all the birds to the right of the dead bird jump down on wire number *i*<=+<=1, if there exists no such wire they fly away. 

Shaass has shot *m* birds. You're given the initial number of birds on each wire, tell him how many birds are sitting on each wire after the shots.

Input Specification:
The first line of the input contains an integer *n*, (1<=≤<=*n*<=≤<=100). The next line contains a list of space-separated integers *a*1,<=*a*2,<=...,<=*a**n*, (0<=≤<=*a**i*<=≤<=100). 

The third line contains an integer *m*, (0<=≤<=*m*<=≤<=100). Each of the next *m* lines contains two integers *x**i* and *y**i*. The integers mean that for the *i*-th time Shaass shoot the *y**i*-th (from left) bird on the *x**i*-th wire, (1<=≤<=*x**i*<=≤<=*n*,<=1<=≤<=*y**i*). It's guaranteed there will be at least *y**i* birds on the *x**i*-th wire at that moment.

Output Specification:
On the *i*-th line of the output print the number of birds on the *i*-th wire.

Demo Input:
['5\n10 10 10 10 10\n5\n2 5\n3 13\n2 12\n1 13\n4 6\n', '3\n2 4 1\n1\n2 2\n']

Demo Output:
['0\n12\n5\n0\n16\n', '3\n0\n3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given n orders, each order consist in pickup and delivery services. 
Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i). 
Since the answer may be too large, return it modulo 10^9 + 7.
 
Example 1:
Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

Example 2:
Input: n = 2
Output: 6
Explanation: All possible orders: 
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.

Example 3:
Input: n = 3
Output: 90

 
Constraints:

1 <= n <= 500

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has infinite coins in denominations of rupees 5 and rupees 10.

Find the minimum number of coins Chef needs, to pay exactly X rupees. If it is impossible to pay X rupees in denominations of rupees 5 and 10 only, print -1.

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single integer X.

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

For each test case, print a single integer - the minimum number of coins Chef needs, to pay exactly X rupees. If it is impossible to pay X rupees in denominations of rupees 5 and 10 only, print -1.

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

$1 ≤ T ≤ 1000$
$1 ≤ X ≤ 1000$

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

Subtask 1 (100 points): Original constraints.

----- Sample Input 1 ------ 
3
50
15
8

----- Sample Output 1 ------ 
5
2
-1

----- explanation 1 ------ 
Test Case $1$: Chef would require at least $5$ coins to pay $50$ rupees. All these coins would be of rupees $10$.

Test Case $2$: Chef would require at least $2$ coins to pay $15$ rupees. Out of these, $1$ coin would be of rupees $10$ and $1$ coin would be of rupees $5$.

Test Case $3$: Chef cannot pay exactly $8$ rupees in denominations of rupees $5$ and $10$ only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's give it a try! You have a linked list and you have to implement the functionalities push and pop of stack using this given linked list. Your task is to use the class as shown in the comments in the code editor and complete the functions push() and pop() to implement a stack. 
Example 1:
Input: 
push(2)
push(3)
pop()
push(4) 
pop()
Output: 3 4
Explanation: 
push(2)    the stack will be {2}
push(3)    the stack will be {2 3}
pop()      poped element will be 3,
           the stack will be {2}
push(4)    the stack will be {2 4}
pop()      poped element will be 4
Example 2:
Input: 
pop()
push(4)
push(5)
pop()
Output: -1 5
Your Task: You are required to complete two methods push() and pop(). The push() method takes one argument, an integer 'x' to be pushed into the stack and pop() which returns an integer present at the top and popped out from the stack. If the stack is empty then return -1 from the pop() method.
Expected Time Complexity: O(1) for both push() and pop().
Expected Auxiliary Space: O(1) for both push() and pop().
Constraints:
1 <= Q <= 100
1 <= x <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gerald is very particular to eight point sets. He thinks that any decent eight point set must consist of all pairwise intersections of three distinct integer vertical straight lines and three distinct integer horizontal straight lines, except for the average of these nine points. In other words, there must be three integers x_1, x_2, x_3 and three more integers y_1, y_2, y_3, such that x_1 < x_2 < x_3, y_1 < y_2 < y_3 and the eight point set consists of all points (x_{i}, y_{j}) (1 ≤ i, j ≤ 3), except for point (x_2, y_2).

You have a set of eight points. Find out if Gerald can use this set?


-----Input-----

The input consists of eight lines, the i-th line contains two space-separated integers x_{i} and y_{i} (0 ≤ x_{i}, y_{i} ≤ 10^6). You do not have any other conditions for these points.


-----Output-----

In a single line print word "respectable", if the given set of points corresponds to Gerald's decency rules, and "ugly" otherwise.


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

Output
respectable

Input
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0

Output
ugly

Input
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2

Output
ugly

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Zane the wizard is going to perform a magic show shuffling the cups.

There are *n* cups, numbered from 1 to *n*, placed along the *x*-axis on a table that has *m* holes on it. More precisely, cup *i* is on the table at the position *x*<==<=*i*.

The problematic bone is initially at the position *x*<==<=1. Zane will confuse the audience by swapping the cups *k* times, the *i*-th time of which involves the cups at the positions *x*<==<=*u**i* and *x*<==<=*v**i*. If the bone happens to be at the position where there is a hole at any time, it will fall into the hole onto the ground and will not be affected by future swapping operations.

Do not forget that Zane is a wizard. When he swaps the cups, he does not move them ordinarily. Instead, he teleports the cups (along with the bone, if it is inside) to the intended positions. Therefore, for example, when he swaps the cup at *x*<==<=4 and the one at *x*<==<=6, they will not be at the position *x*<==<=5 at any moment during the operation.

Zane’s puppy, Inzane, is in trouble. Zane is away on his vacation, and Inzane cannot find his beloved bone, as it would be too exhausting to try opening all the cups. Inzane knows that the Codeforces community has successfully helped Zane, so he wants to see if it could help him solve his problem too. Help Inzane determine the final position of the bone.

Input Specification:
The first line contains three integers *n*, *m*, and *k* (2<=≤<=*n*<=≤<=106, 1<=≤<=*m*<=≤<=*n*, 1<=≤<=*k*<=≤<=3·105) — the number of cups, the number of holes on the table, and the number of swapping operations, respectively.

The second line contains *m* distinct integers *h*1,<=*h*2,<=...,<=*h**m* (1<=≤<=*h**i*<=≤<=*n*) — the positions along the *x*-axis where there is a hole on the table.

Each of the next *k* lines contains two integers *u**i* and *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*, *u**i*<=≠<=*v**i*) — the positions of the cups to be swapped.

Output Specification:
Print one integer — the final position along the *x*-axis of the bone.

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

Demo Output:
['1', '2']

Note:
In the first sample, after the operations, the bone becomes at *x* = 2, *x* = 5, *x* = 7, and *x* = 1, respectively.

In the second sample, after the first operation, the bone becomes at *x* = 2, and falls into the hole onto the ground.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob is decorating his kitchen, more precisely, the floor. He has found a prime candidate for the tiles he will use. They come in a simple form factor — a square tile that is diagonally split into white and black part as depicted in the figure below. [Image] 

The dimension of this tile is perfect for this kitchen, as he will need exactly $w \times h$ tiles without any scraps. That is, the width of the kitchen is $w$ tiles, and the height is $h$ tiles. As each tile can be rotated in one of four ways, he still needs to decide on how exactly he will tile the floor. There is a single aesthetic criterion that he wants to fulfil: two adjacent tiles must not share a colour on the edge — i.e. one of the tiles must have a white colour on the shared border, and the second one must be black. [Image] The picture on the left shows one valid tiling of a $3 \times 2$ kitchen. The picture on the right shows an invalid arrangement, as the bottom two tiles touch with their white parts. 

Find the number of possible tilings. As this number may be large, output its remainder when divided by $998244353$ (a prime number). 


-----Input-----

The only line contains two space separated integers $w$, $h$ ($1 \leq w,h \leq 1\,000$) — the width and height of the kitchen, measured in tiles.


-----Output-----

Output a single integer $n$ — the remainder of the number of tilings when divided by $998244353$.


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

Output
16

Input
2 4

Output
64

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

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
Tom is interested in power consumption of his favourite laptop. His laptop has three modes. In normal mode laptop consumes *P*1 watt per minute. *T*1 minutes after Tom moved the mouse or touched the keyboard for the last time, a screensaver starts and power consumption changes to *P*2 watt per minute. Finally, after *T*2 minutes from the start of the screensaver, laptop switches to the "sleep" mode and consumes *P*3 watt per minute. If Tom moves the mouse or touches the keyboard when the laptop is in the second or in the third mode, it switches to the first (normal) mode. Tom's work with the laptop can be divided into *n* time periods [*l*1,<=*r*1],<=[*l*2,<=*r*2],<=...,<=[*l**n*,<=*r**n*]. During each interval Tom continuously moves the mouse and presses buttons on the keyboard. Between the periods Tom stays away from the laptop. Find out the total amount of power consumed by the laptop during the period [*l*1,<=*r**n*].

Input Specification:
The first line contains 6 integer numbers *n*, *P*1, *P*2, *P*3, *T*1, *T*2 (1<=≤<=*n*<=≤<=100,<=0<=≤<=*P*1,<=*P*2,<=*P*3<=≤<=100,<=1<=≤<=*T*1,<=*T*2<=≤<=60). The following *n* lines contain description of Tom's work. Each *i*-th of these lines contains two space-separated integers *l**i* and *r**i* (0<=≤<=*l**i*<=&lt;<=*r**i*<=≤<=1440, *r**i*<=&lt;<=*l**i*<=+<=1 for *i*<=&lt;<=*n*), which stand for the start and the end of the *i*-th period of work.

Output Specification:
Output the answer to the problem.

Demo Input:
['1 3 2 1 5 10\n0 10\n', '2 8 4 2 5 10\n20 30\n50 100\n']

Demo Output:
['30', '570']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A binary string is a string where each character is either 0 or 1. Two binary strings $a$ and $b$ of equal length are similar, if they have the same character in some position (there exists an integer $i$ such that $a_i = b_i$). For example:  10010 and 01111 are similar (they have the same character in position $4$);  10010 and 11111 are similar;  111 and 111 are similar;  0110 and 1001 are not similar. 

You are given an integer $n$ and a binary string $s$ consisting of $2n-1$ characters. Let's denote $s[l..r]$ as the contiguous substring of $s$ starting with $l$-th character and ending with $r$-th character (in other words, $s[l..r] = s_l s_{l + 1} s_{l + 2} \dots s_r$).

You have to construct a binary string $w$ of length $n$ which is similar to all of the following strings: $s[1..n]$, $s[2..n+1]$, $s[3..n+2]$, ..., $s[n..2n-1]$.


-----Input-----

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

The first line of each test case contains a single integer $n$ ($1 \le n \le 50$).

The second line of each test case contains the binary string $s$ of length $2n - 1$. Each character $s_i$ is either 0 or 1.


-----Output-----

For each test case, print the corresponding binary string $w$ of length $n$. If there are multiple such strings — print any of them. It can be shown that at least one string $w$ meeting the constraints always exists.


-----Example-----
Input
4
1
1
3
00000
4
1110000
2
101

Output
1
000
1010
00



-----Note-----

The explanation of the sample case (equal characters in equal positions are bold):

The first test case:   $\mathbf{1}$ is similar to $s[1..1] = \mathbf{1}$. 

The second test case:   $\mathbf{000}$ is similar to $s[1..3] = \mathbf{000}$;  $\mathbf{000}$ is similar to $s[2..4] = \mathbf{000}$;  $\mathbf{000}$ is similar to $s[3..5] = \mathbf{000}$. 

The third test case:   $\mathbf{1}0\mathbf{10}$ is similar to $s[1..4] = \mathbf{1}1\mathbf{10}$;  $\mathbf{1}01\mathbf{0}$ is similar to $s[2..5] = \mathbf{1}10\mathbf{0}$;  $\mathbf{10}1\mathbf{0}$ is similar to $s[3..6] = \mathbf{10}0\mathbf{0}$;  $1\mathbf{0}1\mathbf{0}$ is similar to $s[4..7] = 0\mathbf{0}0\mathbf{0}$. 

The fourth test case:   $0\mathbf{0}$ is similar to $s[1..2] = 1\mathbf{0}$;  $\mathbf{0}0$ is similar to $s[2..3] = \mathbf{0}1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Having learned the multiplication table, Takahashi can multiply two integers between 1 and 9 (inclusive) together.
Given an integer N, determine whether N can be represented as the product of two integers between 1 and 9. If it can, print Yes; if it cannot, print No.

-----Constraints-----
 - 1 \leq N \leq 100
 - N is an integer.

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

-----Output-----
If N can be represented as the product of two integers between 1 and 9 (inclusive), print Yes; if it cannot, print No.

-----Sample Input-----
10

-----Sample Output-----
Yes

10 can be represented as, for example, 2 \times 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mohit's girlfriend is playing a game with Nicky. The description of the game is as follows:
- Initially on a table Player 1 will put N gem-stones.
- Players will play alternatively, turn by turn.
- At each move a player can take at most M gem-stones (at least 1 gem-stone must be taken) from the available gem-stones on the table.(Each gem-stone has same cost.)
- Each players gem-stone are gathered in player's side.
- The player that empties the table purchases food from it (using all his gem-stones; one gem-stone can buy one unit of food), and the other one puts all his gem-stones back on to the table. Again the game continues with the "loser" player starting.
- The game continues until all the gem-stones are used to buy food.
- The main objective of the game is to consume maximum units of food.

	Mohit's girlfriend is weak in mathematics and prediction so she asks help from Mohit, in return she shall kiss Mohit. Mohit task is to predict the maximum units of food her girlfriend can eat, if, she starts first. Being the best friend of Mohit, help him in predicting the answer.

-----Input-----
- Single line contains two space separated integers N and M.

-----Output-----
- The maximum units of food Mohit's girlfriend can eat.

-----Constraints and Subtasks-----
- 1 <= M <= N <= 100
Subtask 1: 10 points
- 1 <= M <= N <= 5
Subtask 2: 20 points
- 1 <= M <= N <= 10
Subtask 3: 30 points
- 1 <= M <= N <= 50
Subtask 3: 40 points
- Original Constraints.

-----Example-----
Input:
4 2

Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Nastya and an Array

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Nastya owns too many arrays now, so she wants to delete the least important of them. However, she discovered that this array is magic! Nastya now knows that the array has the following properties:
 -  In one second we can add an arbitrary (possibly negative) integer to all elements of the array that are not equal to zero. -  When all elements of the array become equal to zero, the array explodes. 
Nastya is always busy, so she wants to explode the array as fast as possible. Compute the minimum time in which the array can be exploded.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=105) — the size of the array.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (<=-<=105<=≤<=*a**i*<=≤<=105) — the elements of the array.

Output Specification:
Print a single integer — the minimum number of seconds needed to make all elements of the array equal to zero.

Demo Input:
['5\n1 1 1 1 1\n', '3\n2 0 -1\n', '4\n5 -6 -5 1\n']

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

Note:
In the first example you can add  - 1 to all non-zero elements in one second and make them equal to zero.

In the second example you can add  - 2 on the first second, then the array becomes equal to [0, 0,  - 3]. On the second second you can add 3 to the third (the only non-zero) element.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One player came to a casino and found a slot machine where everything depends only on how he plays. The rules follow.

A positive integer $a$ is initially on the screen. The player can put a coin into the machine and then add $1$ to or subtract $1$ from any two adjacent digits. All digits must remain from $0$ to $9$ after this operation, and the leading digit must not equal zero. In other words, it is forbidden to add $1$ to $9$, to subtract $1$ from $0$ and to subtract $1$ from the leading $1$. Once the number on the screen becomes equal to $b$, the player wins the jackpot. $a$ and $b$ have the same number of digits.

Help the player to determine the minimal number of coins he needs to spend in order to win the jackpot and tell how to play.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 10^5$) standing for the length of numbers $a$ and $b$.

The next two lines contain numbers $a$ and $b$, each one on a separate line ($10^{n-1} \le a, b < 10^n$).


-----Output-----

If it is impossible to win the jackpot, print a single integer $-1$.

Otherwise, the first line must contain the minimal possible number $c$ of coins the player has to spend.

$\min(c, 10^5)$ lines should follow, $i$-th of them containing two integers $d_i$ and $s_i$ ($1\le d_i\le n - 1$, $s_i = \pm 1$) denoting that on the $i$-th step the player should add $s_i$ to the $d_i$-th and $(d_i + 1)$-st digits from the left (e. g. $d_i = 1$ means that two leading digits change while $d_i = n - 1$ means that there are two trailing digits which change).

Please notice that the answer may be very big and in case $c > 10^5$ you should print only the first $10^5$ moves. Your answer is considered correct if it is possible to finish your printed moves to win the jackpot in the minimal possible number of coins. In particular, if there are multiple ways to do this, you can output any of them.


-----Examples-----
Input
3
223
322

Output
2
1 1
2 -1

Input
2
20
42

Output
2
1 1
1 1

Input
2
35
44

Output
-1



-----Note-----

In the first example, we can make a +1 operation on the two first digits, transforming number $\textbf{22}3$ into $\textbf{33}3$, and then make a -1 operation on the last two digits, transforming $3\textbf{33}$ into $3\textbf{22}$.

It's also possible to do these operations in reverse order, which makes another correct answer.

In the last example, one can show that it's impossible to transform $35$ into $44$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A competitive eater, Alice is scheduling some practices for an eating contest on a magical calendar. The calendar is unusual because a week contains not necessarily $7$ days!

In detail, she can choose any integer $k$ which satisfies $1 \leq k \leq r$, and set $k$ days as the number of days in a week.

Alice is going to paint some $n$ consecutive days on this calendar. On this calendar, dates are written from the left cell to the right cell in a week. If a date reaches the last day of a week, the next day's cell is the leftmost cell in the next (under) row.

She wants to make all of the painted cells to be connected by side. It means, that for any two painted cells there should exist at least one sequence of painted cells, started in one of these cells, and ended in another, such that any two consecutive cells in this sequence are connected by side.

Alice is considering the shape of the painted cells. Two shapes are the same if there exists a way to make them exactly overlapped using only parallel moves, parallel to the calendar's sides.

For example, in the picture, a week has $4$ days and Alice paints $5$ consecutive days. [1] and [2] are different shapes, but [1] and [3] are equal shapes. [Image] 

Alice wants to know how many possible shapes exists if she set how many days a week has and choose consecutive $n$ days and paints them in calendar started in one of the days of the week. As was said before, she considers only shapes, there all cells are connected by side.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

For each test case, the only line contains two integers $n$, $r$ ($1 \le n \le 10^9, 1 \le r \le 10^9$).


-----Output-----

For each test case, print a single integer  — the answer to the problem.

Please note, that the answer for some test cases won't fit into $32$-bit integer type, so you should use at least $64$-bit integer type in your programming language.


-----Example-----
Input
5
3 4
3 2
3 1
13 7
1010000 9999999

Output
4
3
1
28
510049495001



-----Note-----

In the first test case, Alice can set $1,2,3$ or $4$ days as the number of days in a week.

There are $6$ possible paintings shown in the picture, but there are only $4$ different shapes. So, the answer is $4$. Notice that the last example in the picture is an invalid painting because all cells are not connected by sides. [Image] 

In the last test case, be careful with the overflow issue, described in the output format.

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