vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Grammar Lessons

Time Limit: 5 seconds

Memory Limit: 256 megabytes

Problem Description:
Petya got interested in grammar on his third year in school. He invented his own language called Petya's. Petya wanted to create a maximally simple language that would be enough to chat with friends, that's why all the language's grammar can be described with the following set of rules:
-  There are three parts of speech: the adjective, the noun, the verb. Each word in his language is an adjective, noun or verb. -  There are two genders: masculine and feminine. Each word in his language has gender either masculine or feminine. -  Masculine adjectives end with -lios, and feminine adjectives end with -liala. -  Masculine nouns end with -etr, and feminime nouns end with -etra. -  Masculine verbs end with -initis, and feminime verbs end with -inites. -  Thus, each word in the Petya's language has one of the six endings, given above. There are no other endings in Petya's language. -  It is accepted that the whole word consists of an ending. That is, words "lios", "liala", "etr" and so on belong to the Petya's language. -  There aren't any punctuation marks, grammatical tenses, singular/plural forms or other language complications. -  A sentence is either exactly one valid language word or exactly one statement. 
Statement is any sequence of the Petya's language, that satisfy both conditions:
-  Words in statement follow in the following order (from the left to the right): zero or more adjectives followed by exactly one noun followed by zero or more verbs. -  All words in the statement should have the same gender.
After Petya's friend Vasya wrote instant messenger (an instant messaging program) that supported the Petya's language, Petya wanted to add spelling and grammar checking to the program. As Vasya was in the country and Petya didn't feel like waiting, he asked you to help him with this problem. Your task is to define by a given sequence of words, whether it is true that the given text represents exactly one sentence in Petya's language.

Input Specification:
The first line contains one or more words consisting of lowercase Latin letters. The overall number of characters (including letters and spaces) does not exceed 105.

It is guaranteed that any two consecutive words are separated by exactly one space and the input data do not contain any other spaces. It is possible that given words do not belong to the Petya's language.

Output Specification:
If some word of the given text does not belong to the Petya's language or if the text contains more that one sentence, print "NO" (without the quotes). Otherwise, print "YES" (without the quotes).

Demo Input:
['petr\n', 'etis atis animatis etis atis amatis\n', 'nataliala kataliala vetra feinites\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Malek lives in an apartment block with 100 floors numbered from 0 to 99. The apartment has an elevator with a digital counter showing the floor that the elevator is currently on. The elevator shows each digit of a number with 7 light sticks by turning them on or off. The picture below shows how the elevator shows each digit.[Image]

One day when Malek wanted to go from floor 88 to floor 0 using the elevator he noticed that the counter shows number 89 instead of 88. Then when the elevator started moving the number on the counter changed to 87. After a little thinking Malek came to the conclusion that there is only one explanation for this: One of the sticks of the counter was broken. Later that day Malek was thinking about the broken stick and suddenly he came up with the following problem.

Suppose the digital counter is showing number n. Malek calls an integer x (0 ≤ x ≤ 99) good if it's possible that the digital counter was supposed to show x but because of some(possibly none) broken sticks it's showing n instead. Malek wants to know number of good integers for a specific n. So you must write a program that calculates this number. Please note that the counter always shows two digits.


-----Input-----

The only line of input contains exactly two digits representing number n (0 ≤ n ≤ 99). Note that n may have a leading zero.


-----Output-----

In the only line of the output print the number of good integers.


-----Examples-----
Input
89

Output
2

Input
00

Output
4

Input
73

Output
15



-----Note-----

In the first sample the counter may be supposed to show 88 or 89.

In the second sample the good integers are 00, 08, 80 and 88.

In the third sample the good integers are 03, 08, 09, 33, 38, 39, 73, 78, 79, 83, 88, 89, 93, 98, 99.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's consider a rooted binary tree with the following properties:
- The number of nodes and edges in the tree is infinite
- The tree root is labeled by $1$
- A node labeled by $v$ has two children: $2 \cdot v$ (the left child of $v$), and $2 \cdot v + 1$ (the right child of $v$).
Here is an image of the first several layers of such a tree:

Let's consider four operations that you are allowed to apply during the tree traversal:
- move to the left child - move from $v$ to $2 \cdot v$
- move to the right child - move from $v$ to $2 \cdot v + 1$
- move to the parent as a left child - move from $v$ to $\frac{v}{2}$ if $v$ is an even integer
- move to the parent as a right child - move from $v$ to $\frac{v - 1}{2}$ if $v$ is an odd integer
It can be proven, that for any pair of nodes $u$ and $v$, there is only one sequence of commands that moves from $u$ to $v$ and visits each node of the tree at most once. Let's call such a sequence of commands a path configuration for a pair of nodes $(u, v)$.
You are asked to process a series of the following queries: 
You are given three integers $n$, $u$ and $v$ ($1 \leq u, v \leq n$). Count the pairs of nodes $(w, t)$ ($1 \leq w, t \leq n$) such that the path configuration for $(w, t)$ is the same with the path configuration for $(u, v)$.

-----Input-----
- The first line of input contains a single integer $Q$, denoting the number of queries to process.
- Each of the next $Q$ lines contains three space-separated integers $n$, $u$ and $v$ denoting a query.

-----Output-----
For each query, print the answer on a separate line.

-----Constraints-----
- $1 \leq Q \leq 2 \cdot 10^4$
- $1 \leq u, v \leq n \leq 10^{9}$

-----Example Input-----
3
11 9 11
10 2 2
8 1 8

-----Example Output-----
2
10
1

-----Explanation-----
In the first query from the example test case, you should count pairs $(5, 7)$ and $(9, 11)$.
In the second query from the example test case, you should count the following pairs: $(1, 1)$, $(2, 2)$, $(3, 3)$, $(4, 4)$, $(5, 5)$, $(6, 6)$, $(7, 7)$, $(8, 8)$, $(9, 9)$ and $(10, 10)$.
In the third query from the example test case, you should only count a pair $(1, 8)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It’s the year 2552, the Humans just won a war against a very powerful alien race that had invaded our solar system. The Human army is in celebration mode! 

The army has n soldiers. The soldiers are numbers from 1 to n. The army has a superiority hierarchy. Every soldier has one immediate superior. The superior of a superior of a soldier is also a superior to that soldier. So, a soldier may have one or more superiors but only one immediate superior.

Every soldier has to congratulate every other soldier. For a pair of soldiers if one of them is the superior of the other, they will shake hands. Otherwise, they will bump their fists.

You are given the list of immediate superior of all soldiers. Your job is to tell how many handshakes and fist bumps will be there.

NOTE: Among all soldiers there is one soldier who does not have any superior. He is the commander of the whole army.

Input:

The first line of the input contains t, the number of test cases.

The first line of each test case contains n, the number of soldiers. The next line contains n space separated integers. The ith integer represents the immediate superior of the ith soldier.

The immediate superior of the commander of the army will be '0'.

Output:

Output two space separated integers, the number of handshakes and the number of fist bumps.

Constraints:

1 ≤ t ≤ 10

1 ≤ n ≤ 100000

It is guaranteed that the commander of the army is a superior of all soldiers.

SAMPLE INPUT
2
3
0 1 1
2
2 0

SAMPLE OUTPUT
2 1
1 0

Explanation

1st test case:
Handshakes between (1,2), (1,3). 
Fist bumps between (2,3)

2nd test case:
Handshake between (1,2)
No fist bumps

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There was a big bank robbery in Tablecity. In order to catch the thief, the President called none other than Albert – Tablecity’s Chief of Police. Albert does not know where the thief is located, but he does know how he moves.

Tablecity can be represented as 1000 × 2 grid, where every cell represents one district. Each district has its own unique name “(X, Y)”, where X and Y are the coordinates of the district in the grid. The thief’s movement is as 

Every hour the thief will leave the district (X, Y) he is currently hiding in, and move to one of the districts: (X - 1, Y), (X + 1, Y), (X - 1, Y - 1), (X - 1, Y + 1), (X + 1, Y - 1), (X + 1, Y + 1) as long as it exists in Tablecity. 

Below is an example of thief’s possible movements if he is located in district (7,1):

[Image]

Albert has enough people so that every hour he can pick any two districts in Tablecity and fully investigate them, making sure that if the thief is located in one of them, he will get caught. Albert promised the President that the thief will be caught in no more than 2015 hours and needs your help in order to achieve that.


-----Input-----

There is no input for this problem. 


-----Output-----

The first line of output contains integer N – duration of police search in hours. Each of the following N lines contains exactly 4 integers X_{i}1, Y_{i}1, X_{i}2, Y_{i}2 separated by spaces, that represent 2 districts (X_{i}1, Y_{i}1), (X_{i}2, Y_{i}2) which got investigated during i-th hour. Output is given in chronological order (i-th line contains districts investigated during i-th hour) and should guarantee that the thief is caught in no more than 2015 hours, regardless of thief’s initial position and movement.  N ≤ 2015  1 ≤ X ≤ 1000  1 ≤ Y ≤ 2 


-----Examples-----
Input
В этой задаче нет примеров ввода-вывода.
This problem doesn't have sample input and output.
Output
Смотрите замечание ниже.
See the note below.


-----Note-----

Let's consider the following output:

2

5 1 50 2

8 1 80 2

This output is not guaranteed to catch the thief and is not correct. It is given to you only to show the expected output format. There exists a combination of an initial position and a movement strategy such that the police will not catch the thief.

Consider the following initial position and thief’s movement:

In the first hour, the thief is located in district (1,1). Police officers will search districts (5,1) and (50,2) and will not find him.

At the start of the second hour, the thief moves to district (2,2). Police officers will search districts (8,1) and (80,2) and will not find him.

Since there is no further investigation by the police, the thief escaped!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Inna loves sweets very much. That's why she decided to play a game called "Sweet Matrix".

Inna sees an n × m matrix and k candies. We'll index the matrix rows from 1 to n and the matrix columns from 1 to m. We'll represent the cell in the i-th row and j-th column as (i, j). Two cells (i, j) and (p, q) of the matrix are adjacent if |i - p| + |j - q| = 1. A path is a sequence of the matrix cells where each pair of neighbouring cells in the sequence is adjacent. We'll call the number of cells in the sequence the path's length.

Each cell of the matrix can have at most one candy. Initiallly, all the cells are empty. Inna is trying to place each of the k candies in the matrix one by one. For each candy Inna chooses cell (i, j) that will contains the candy, and also chooses the path that starts in cell (1, 1) and ends in cell (i, j) and doesn't contain any candies. After that Inna moves the candy along the path from cell (1, 1) to cell (i, j), where the candy stays forever. If at some moment Inna can't choose a path for the candy, she loses. If Inna can place all the candies in the matrix in the described manner, then her penalty equals the sum of lengths of all the paths she has used.

Help Inna to minimize the penalty in the game.


-----Input-----

The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 50, 1 ≤ k ≤ n·m).


-----Output-----

In the first line print an integer — Inna's minimum penalty in the game.

In the next k lines print the description of the path for each candy. The description of the path of the candy that is placed i-th should follow on the i-th line. The description of a path is a sequence of cells. Each cell must be written in the format (i, j), where i is the number of the row and j is the number of the column. You are allowed to print extra whitespaces in the line. If there are multiple optimal solutions, print any of them.

Please follow the output format strictly! If your program passes the first pretest, then the output format is correct.


-----Examples-----
Input
4 4 4

Output
8
(1,1) (2,1) (2,2)
(1,1) (1,2)
(1,1) (2,1)
(1,1)



-----Note-----

Note to the sample. Initially the matrix is empty. Then Inna follows her first path, the path penalty equals the number of cells in it — 3. Note that now no path can go through cell (2, 2), as it now contains a candy. The next two candies go to cells (1, 2) and (2, 1). Inna simply leaves the last candy at cell (1, 1), the path contains only this cell. The total penalty is: 3 + 2 + 2 + 1 = 8.

Note that Inna couldn't use cell (1, 1) to place, for instance, the third candy as in this case she couldn't have made the path for the fourth candy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a New York City coffee house called Central Perk, we're introduced to six friends: chef Monica Geller, data controller Chandler Bing who lives across the hall from Monica, Chandler's roommate/actor Joey Tribbiani, Monica's brother Ross Geller, new ageist Phoebe Buffay, and "born to be a wife" Rachel Green.

Chef wants to divide N cookies between the six friends such that:
Each friend gets at least one cookie.
No two friends get the same number of cookies.

Find if it is possible for Chef to do so.

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains of a single line of input, one integers N.

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

For each test case print "YES" if Chef can divide the cookies according to the given rules, else print "NO".

You may print each character of each string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{3}$

----- Sample Input 1 ------ 
3
42
5
909
----- Sample Output 1 ------ 
YES
NO
YES
----- explanation 1 ------ 
Test case 1: One possible way of distribution would be $2, 4, 6, 8, 10, 12$.

Test case 2: It is impossible to divide $5$ cookies among six friends according to given rules.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is currently standing at stair 0 and he wants to reach stair numbered X.

Chef can climb either Y steps or 1 step in one move.  
Find the minimum number of moves required by him to reach exactly the stair numbered X.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input containing two space separated integers X and Y denoting the number of stair Chef wants to reach and the number of stairs he can climb in one move.

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

For each test case, output the minimum number of moves required by him to reach exactly the stair numbered X.

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

$1 ≤ T ≤ 500$
$1 ≤ X, Y ≤ 100$

----- Sample Input 1 ------ 
4
4 2
8 3
3 4
2 1

----- Sample Output 1 ------ 
2
4
3
2

----- explanation 1 ------ 
Test case $1$: Chef can make $2$ moves and climb $2$ steps in each move to reach stair numbered $4$.

Test case $2$: Chef can make a minimum of $4$ moves. He can climb $3$ steps in $2$ of those moves and $1$ step each in remaining $2$ moves to reach stair numbered $8$.

Test case $3$: Chef can make $3$ moves and climb $1$ step in each move to reach stair numbered $3$.

Test case $4$: Chef can make $2$ moves and climb $1$ step in each move to reach stair numbered $2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
Given an array `arr`, find the maximal value of `k` such `a[i] mod k` = `a[j] mod k` for all valid values of i and j.

If it's impossible to find such number (there's an infinite number of `k`s), return `-1` instead.


# Input/Output

`[input]` integer array `arr`

A non-empty array of positive integer.

`2 <= arr.length <= 10`

`1 <= arr[i] <= 100`

`[output]` an integer

The maximum value of `k` or `-1` if there is none.


# Example

For `arr = [1, 2, 3]`, the output should be `1`.

`1` is the only k which satisfies the given conditions.

For `arr = [1, 1, 1]`, the output should be `-1`.

`1 % k = 1` for `any k > 1`, so it's impossible to find the maximum.

For `arr = [5, 2, 8]`, the output should be `3`.

`5 % 3 == 2 % 3 == 8 % 3 == 2`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call a sequence good if the sum of all its elements is $0$.
You have a sequence of integers $A_1, A_2, \ldots, A_N$. You may perform any number of operations on this sequence (including zero). In one operation, you should choose a valid index $i$ and decrease $A_i$ by $i$. Can you make the sequence good using these operations?

-----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 line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing the string "YES" if it is possible to make the given sequence good or "NO" if it is impossible.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 10$
- $|A_i| \le 100$ for each valid $i$

-----Subtasks-----
Subtask #1 (10 points): $N = 1$
Subtask #2 (30 points): $N \le 2$
Subtask #3 (60 points): original constraints

-----Example Input-----
2
1
-1
2
1 2

-----Example Output-----
NO
YES

-----Explanation-----
Example case 2: We can perform two operations ― subtract $1$ from $A_1$ and $2$ from $A_2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya has got 2n cards, each card contains some integer. The numbers on the cards can be the same. Let's index all cards by consecutive integers from 1 to 2n. We'll denote the number that is written on a card with number i, as ai. In order to play one entertaining game with his friends, Petya needs to split the cards into pairs so that each pair had equal numbers on the cards. Help Petya do that.

Input

The first line contains integer n (1 ≤ n ≤ 3·105). The second line contains the sequence of 2n positive integers a1, a2, ..., a2n (1 ≤ ai ≤ 5000) — the numbers that are written on the cards. The numbers on the line are separated by single spaces.

Output

If it is impossible to divide the cards into pairs so that cards in each pair had the same numbers, print on a single line integer -1. But if the required partition exists, then print n pairs of integers, a pair per line — the indices of the cards that form the pairs.

Separate the numbers on the lines by spaces. You can print the pairs and the numbers in the pairs in any order. If there are multiple solutions, print any of them.

Examples

Input

3
20 30 10 30 20 10


Output

4 2
1 5
6 3


Input

1
1 2


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this task you need to process a set of stock exchange orders and use them to create order book.

An order is an instruction of some participant to buy or sell stocks on stock exchange. The order number i has price p_{i}, direction d_{i} — buy or sell, and integer q_{i}. This means that the participant is ready to buy or sell q_{i} stocks at price p_{i} for one stock. A value q_{i} is also known as a volume of an order.

All orders with the same price p and direction d are merged into one aggregated order with price p and direction d. The volume of such order is a sum of volumes of the initial orders.

An order book is a list of aggregated orders, the first part of which contains sell orders sorted by price in descending order, the second contains buy orders also sorted by price in descending order.

An order book of depth s contains s best aggregated orders for each direction. A buy order is better if it has higher price and a sell order is better if it has lower price. If there are less than s aggregated orders for some direction then all of them will be in the final order book.

You are given n stock exhange orders. Your task is to print order book of depth s for these orders.


-----Input-----

The input starts with two positive integers n and s (1 ≤ n ≤ 1000, 1 ≤ s ≤ 50), the number of orders and the book depth.

Next n lines contains a letter d_{i} (either 'B' or 'S'), an integer p_{i} (0 ≤ p_{i} ≤ 10^5) and an integer q_{i} (1 ≤ q_{i} ≤ 10^4) — direction, price and volume respectively. The letter 'B' means buy, 'S' means sell. The price of any sell order is higher than the price of any buy order.


-----Output-----

Print no more than 2s lines with aggregated orders from order book of depth s. The output format for orders should be the same as in input.


-----Examples-----
Input
6 2
B 10 3
S 50 2
S 40 1
S 50 6
B 20 4
B 25 10

Output
S 50 8
S 40 1
B 25 10
B 20 4



-----Note-----

Denote (x, y) an order with price x and volume y. There are 3 aggregated buy orders (10, 3), (20, 4), (25, 10) and two sell orders (50, 8), (40, 1) in the sample.

You need to print no more than two best orders for each direction, so you shouldn't print the order (10 3) having the worst price among buy orders.

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