vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Petya and Java

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Little Petya has recently started attending a programming club. Naturally he is facing the problem of choosing a programming language. After long considerations he realized that Java is the best choice. The main argument in favor of choosing Java was that it has a very large integer data type, called BigInteger.

But having attended several classes of the club, Petya realized that not all tasks require using the BigInteger type. It turned out that in some tasks it is much easier to use small data types. That's why a question arises: "Which integer type to use if one wants to store a positive integer *n*?"

Petya knows only 5 integer types:

1) byte occupies 1 byte and allows you to store numbers from <=-<=128 to 127

2) short occupies 2 bytes and allows you to store numbers from <=-<=32768 to 32767

3) int occupies 4 bytes and allows you to store numbers from <=-<=2147483648 to 2147483647

4) long occupies 8 bytes and allows you to store numbers from <=-<=9223372036854775808 to 9223372036854775807

5) BigInteger can store any integer number, but at that it is not a primitive type, and operations with it are much slower.

For all the types given above the boundary values are included in the value range.

From this list, Petya wants to choose the smallest type that can store a positive integer *n*. Since BigInteger works much slower, Peter regards it last. Help him.

Input Specification:
The first line contains a positive number *n*. It consists of no more than 100 digits and doesn't contain any leading zeros. The number *n* can't be represented as an empty string.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Output Specification:
Print the first type from the list "byte, short, int, long, BigInteger", that can store the natural number *n*, in accordance with the data given above.

Demo Input:
['127\n', '130\n', '123456789101112131415161718192021222324\n']

Demo Output:
['byte\n', 'short\n', 'BigInteger\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Each New Year Timofey and his friends cut down a tree of n vertices and bring it home. After that they paint all the n its vertices, so that the i-th vertex gets color c_{i}.

Now it's time for Timofey birthday, and his mother asked him to remove the tree. Timofey removes the tree in the following way: he takes some vertex in hands, while all the other vertices move down so that the tree becomes rooted at the chosen vertex. After that Timofey brings the tree to a trash can.

Timofey doesn't like it when many colors are mixing together. A subtree annoys him if there are vertices of different color in it. Timofey wants to find a vertex which he should take in hands so that there are no subtrees that annoy him. He doesn't consider the whole tree as a subtree since he can't see the color of the root vertex.

A subtree of some vertex is a subgraph containing that vertex and all its descendants.

Your task is to determine if there is a vertex, taking which in hands Timofey wouldn't be annoyed.


-----Input-----

The first line contains single integer n (2 ≤ n ≤ 10^5) — the number of vertices in the tree.

Each of the next n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), denoting there is an edge between vertices u and v. It is guaranteed that the given graph is a tree.

The next line contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^5), denoting the colors of the vertices.


-----Output-----

Print "NO" in a single line, if Timofey can't take the tree in such a way that it doesn't annoy him.

Otherwise print "YES" in the first line. In the second line print the index of the vertex which Timofey should take in hands. If there are multiple answers, print any of them.


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

Output
YES
2
Input
3
1 2
2 3
1 2 3

Output
YES
2
Input
4
1 2
2 3
3 4
1 2 1 2

Output
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two little greedy bears have found two pieces of cheese in the forest of weight a and b grams, correspondingly. The bears are so greedy that they are ready to fight for the larger piece. That's where the fox comes in and starts the dialog: "Little bears, wait a little, I want to make your pieces equal" "Come off it fox, how are you going to do that?", the curious bears asked. "It's easy", said the fox. "If the mass of a certain piece is divisible by two, then I can eat exactly a half of the piece. If the mass of a certain piece is divisible by three, then I can eat exactly two-thirds, and if the mass is divisible by five, then I can eat four-fifths. I'll eat a little here and there and make the pieces equal". 

The little bears realize that the fox's proposal contains a catch. But at the same time they realize that they can not make the two pieces equal themselves. So they agreed to her proposal, but on one condition: the fox should make the pieces equal as quickly as possible. Find the minimum number of operations the fox needs to make pieces equal.


-----Input-----

The first line contains two space-separated integers a and b (1 ≤ a, b ≤ 10^9). 


-----Output-----

If the fox is lying to the little bears and it is impossible to make the pieces equal, print -1. Otherwise, print the required minimum number of operations. If the pieces of the cheese are initially equal, the required number is 0.


-----Examples-----
Input
15 20

Output
3

Input
14 8

Output
-1

Input
6 6

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A cell phone company is trying out its new model of cell phone. Here's how its structure is: 

The keypad has 11 buttons corresponding to digits from 0 to 9 and one additional button called Add. After pressing any button from 0 to 9, the corresponding digit appears on the screen. The Add button replaces the last two digits appearing on the screen with their sum taken modulo 10. (See sample test for more clarity). If there are less than two digits currently on the screen, pressing Add does nothing.

Each button has a non-negative cost of pressing associated with it. The cost of pressing Add button is always 0. Given the cost of pressing each button and the target phone number, find the minimum cost of feeding that number into the phone screen using a sequence of button presses.

INPUT

The first line of input file consists of an integer T, which indicates the number of test cases. Then the description of T test cases follow. Each test case is described by 3 lines. The first of them contains 10 space separated integers, denoting the cost of pressing buttons from 0 to 9. The second line contains the length of the target phone number. The third line contains the target phone number S itself.

OUTPUT

Print the minimum cost of feeding the phone screen with the target number for each test case in a separate line.

CONSTRAINTS

1 ≤ T ≤ 1000
0 ≤ Cost of any button ≤ 1000
1 ≤ |S|≤ 1000

SAMPLE INPUT
3
3 2 2 3 2 1 1 2 3 3 
3
171
3 2 3 1 1 1 1 3 1 2 
2
16
3 3 3 1 3 1 1 2 3 2 
2
43

SAMPLE OUTPUT
6
3
4

Explanation

For Test Case 1: Button sequence with cost in brackets: Press 6 (1) -> Press 5 (1) -> Press "Add" (0) -> Press 7 (2)  -> Press 6 (1) -> Press 5 (1)-> Press "Add" (0).

Total Cost = 1 + 1 + 0 + 2 + 1 + 1 + 0 = 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef found an array A of N elements. He defines a subarray as *bad* if the maximum element of the subarray is equal to the minimum element of the subarray.

More formally, a subarray [L,R] (1 ≤ L ≤ R ≤ N) is *bad* if \texttt{max}(A_{L}, A_{L+1}, \ldots , A_{R}) = \texttt{min} (A_{L}, A_{L+1}, ... , A_{R}).

Chef is allowed to change at most K elements of the array.  
Find the minimum number of *bad* subarrays Chef can obtain after changing at most K elements of the array.    

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

- First line will contain T, the number of test cases. Then the test cases follow.
- Each test case contains two lines of input, the first line contains two space-separated integers N and K - the number of elements in the array and the maximum number of elements Chef can change respectively.
- The second line contains N space-separated integers A_{1}, A_{2},\ldots, A_{N} - the initial array.

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

For each test case, output the minimum number of *bad* subarrays Chef can obtain after changing at most K elements of the array.

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

$1 ≤ T ≤ 3\cdot 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ N$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3 1
1 2 3
4 2
3 3 3 1
5 1
1 1 1 1 1

----- Sample Output 1 ------ 
3
4
7

----- explanation 1 ------ 
Test case $1$: The minimum number of *bad* subarrays Chef can obtain is $3$. Chef does not need to perform any operations. The subarrays where the maximum element is equal to the minimum element are $[1,1], [2,2],$ and $[3,3]$ where $[L,R]$ denotes the subarray starting at index $L$ and ending at index $R$.

Test case $2$: The minimum number of *bad* subarrays Chef can obtain is $4$. Chef can perform $2$ operations and change the array to $[2, 4, 3, 1]$. The subarrays where the maximum element is equal to the minimum element are $[1,1], [2,2], [3,3],$ and $[4,4]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
How many strings can be obtained by applying the following operation on a string S exactly K times: "choose one lowercase English letter and insert it somewhere"?
The answer can be enormous, so print it modulo (10^9+7).

-----Constraints-----
 - K is an integer between 1 and 10^6 (inclusive).
 - S is a string of length between 1 and 10^6 (inclusive) consisting of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
K
S

-----Output-----
Print the number of strings satisfying the condition, modulo (10^9+7).

-----Sample Input-----
5
oof

-----Sample Output-----
575111451

For example, we can obtain proofend, moonwolf, and onionpuf, while we cannot obtain oofsix, oofelevennn, voxafolt, or fooooooo.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Do you know confetti? They are small discs of colored paper, and people throw them around during parties or festivals. Since people throw lots of confetti, they may end up stacked one on another, so there may be hidden ones underneath.

A handful of various sized confetti have been dropped on a table. Given their positions and sizes, can you tell us how many of them you can see?

The following figure represents the disc configuration for the first sample input, where the bottom disc is still visible.

<image>



Input

The input is composed of a number of configurations of the following form.


n 		
x1 y1 z1
x2 y2 z2
.
.
.
xn yn zn


The first line in a configuration is the number of discs in the configuration (a positive integer not more than 100), followed by one Ine descriptions of each disc: coordinates of its center and radius, expressed as real numbers in decimal notation, with up to 12 digits after the decimal point. The imprecision margin is ±5 × 10-13. That is, it is guaranteed that variations of less than ±5 × 10-13 on input values do not change which discs are visible. Coordinates of all points contained in discs are between -10 and 10.

Confetti are listed in their stacking order, x1 y1 r1 being the bottom one and xn yn rn the top one. You are observing from the top.

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

Output

For each configuration you should output the number of visible confetti on a single line.

Example

Input

3
0 0 0.5
-0.9 0 1.00000000001
0.9 0 1.00000000001
5
0 1 0.5
1 1 1.00000000001
0 2 1.00000000001
-1 1 1.00000000001
0 -0.00001 1.00000000001
5
0 1 0.5
1 1 1.00000000001
0 2 1.00000000001
-1 1 1.00000000001
0 0 1.00000000001
2
0 0 1.0000001
0 0 1
2
0 0 1
0.00000001 0 1
0


Output

3
5
4
2
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Watto, the owner of a spare parts store, has recently got an order for the mechanism that can process strings in a certain way. Initially the memory of the mechanism is filled with n strings. Then the mechanism should be able to process queries of the following type: "Given string s, determine if the memory of the mechanism contains string t that consists of the same number of characters as s and differs from s in exactly one position".

Watto has already compiled the mechanism, all that's left is to write a program for it and check it on the data consisting of n initial lines and m queries. He decided to entrust this job to you.


-----Input-----

The first line contains two non-negative numbers n and m (0 ≤ n ≤ 3·10^5, 0 ≤ m ≤ 3·10^5) — the number of the initial strings and the number of queries, respectively.

Next follow n non-empty strings that are uploaded to the memory of the mechanism.

Next follow m non-empty strings that are the queries to the mechanism.

The total length of lines in the input doesn't exceed 6·10^5. Each line consists only of letters 'a', 'b', 'c'.


-----Output-----

For each query print on a single line "YES" (without the quotes), if the memory of the mechanism contains the required string, otherwise print "NO" (without the quotes).


-----Examples-----
Input
2 3
aaaaa
acacaca
aabaa
ccacacc
caaac

Output
YES
NO
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In order to put away old things and welcome a fresh new year, a thorough cleaning of the house is a must.

Little Tommy finds an old polynomial and cleaned it up by taking it modulo another. But now he regrets doing this...

Given two integers p and k, find a polynomial f(x) with non-negative integer coefficients strictly less than k, whose remainder is p when divided by (x + k). That is, f(x) = q(x)·(x + k) + p, where q(x) is a polynomial (not necessarily with integer coefficients).


-----Input-----

The only line of input contains two space-separated integers p and k (1 ≤ p ≤ 10^18, 2 ≤ k ≤ 2 000).


-----Output-----

If the polynomial does not exist, print a single integer -1, or output two lines otherwise.

In the first line print a non-negative integer d — the number of coefficients in the polynomial.

In the second line print d space-separated integers a_0, a_1, ..., a_{d} - 1, describing a polynomial $f(x) = \sum_{i = 0}^{d - 1} a_{i} \cdot x^{i}$ fulfilling the given requirements. Your output should satisfy 0 ≤ a_{i} < k for all 0 ≤ i ≤ d - 1, and a_{d} - 1 ≠ 0.

If there are many possible solutions, print any of them.


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

Output
7
0 1 0 0 1 1 1

Input
2018 214

Output
3
92 205 1



-----Note-----

In the first example, f(x) = x^6 + x^5 + x^4 + x = (x^5 - x^4 + 3x^3 - 6x^2 + 12x - 23)·(x + 2) + 46.

In the second example, f(x) = x^2 + 205x + 92 = (x - 9)·(x + 214) + 2018.

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

John won the championship of a TV show. He can get some bonuses.

He needs to play a game to determine the amount of his bonus.

Here are some cards in a row. A number is written on each card.

In each turn, John can take a card, but only from the beginning or the end of the row. Then multiply the number on the card by an coefficient 2^(i)(i means the ith turn). The product is John's bonus of current turn.

After all the cards are taken away, the game is over. John's final bonus is the sum of all rounds of bonuses.

Obviously, the order in which John takes the cards will affect the amount of John's final bonus.

Your task is to help John calculate the maximum amount of bonuses he can get.

# Input

- `cards`: An integer array. Each element represents the number on the card.
  - `1 <= cards.length <= 30`
  - `1 <= cards[i] <= 100`


- All inputs are valid.

# Output

An integer. the maximum amount of bonuses John can get.

# Eaxmple

For `cards=[1,2,5]`, the output should be `50`.

```
All possible orders are:
1->2->5   bonus:1x2+2*4+5*8=50
1->5->2   bonus:1x2+5*4+2*8=38
5->1->2   bonus:5*2+1*4+2*8=30
5->2->1   bonus:5*2+2*4+1*8=26
The maximum amount of bonus is 50.
```

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Recently Irina arrived to one of the most famous cities of Berland — the Berlatov city. There are *n* showplaces in the city, numbered from 1 to *n*, and some of them are connected by one-directional roads. The roads in Berlatov are designed in a way such that there are no cyclic routes between showplaces.

Initially Irina stands at the showplace 1, and the endpoint of her journey is the showplace *n*. Naturally, Irina wants to visit as much showplaces as she can during her journey. However, Irina's stay in Berlatov is limited and she can't be there for more than *T* time units.

Help Irina determine how many showplaces she may visit during her journey from showplace 1 to showplace *n* within a time not exceeding *T*. It is guaranteed that there is at least one route from showplace 1 to showplace *n* such that Irina will spend no more than *T* time units passing it.

Input Specification:
The first line of the input contains three integers *n*,<=*m* and *T* (2<=≤<=*n*<=≤<=5000,<=<=1<=≤<=*m*<=≤<=5000,<=<=1<=≤<=*T*<=≤<=109) — the number of showplaces, the number of roads between them and the time of Irina's stay in Berlatov respectively.

The next *m* lines describes roads in Berlatov. *i*-th of them contains 3 integers *u**i*,<=*v**i*,<=*t**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*,<=*u**i*<=≠<=*v**i*,<=1<=≤<=*t**i*<=≤<=109), meaning that there is a road starting from showplace *u**i* and leading to showplace *v**i*, and Irina spends *t**i* time units to pass it. It is guaranteed that the roads do not form cyclic routes.

It is guaranteed, that there is at most one road between each pair of showplaces.

Output Specification:
Print the single integer *k* (2<=≤<=*k*<=≤<=*n*) — the maximum number of showplaces that Irina can visit during her journey from showplace 1 to showplace *n* within time not exceeding *T*, in the first line.

Print *k* distinct integers in the second line — indices of showplaces that Irina will visit on her route, in the order of encountering them.

If there are multiple answers, print any of them.

Demo Input:
['4 3 13\n1 2 5\n2 3 7\n2 4 8\n', '6 6 7\n1 2 2\n1 3 3\n3 6 3\n2 4 2\n4 6 2\n6 5 1\n', '5 5 6\n1 3 3\n3 5 3\n1 2 2\n2 4 3\n4 5 2\n']

Demo Output:
['3\n1 2 4 \n', '4\n1 2 4 6 \n', '3\n1 3 5 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
IT City company developing computer games decided to upgrade its way to reward its employees. Now it looks the following way. After a new game release users start buying it actively, and the company tracks the number of sales with precision to each transaction. Every time when the next number of sales is not divisible by any number from 2 to 10 every developer of this game gets a small bonus.

A game designer Petya knows that the company is just about to release a new game that was partly developed by him. On the basis of his experience he predicts that n people will buy the game during the first month. Now Petya wants to determine how many times he will get the bonus. Help him to know it.


-----Input-----

The only line of the input contains one integer n (1 ≤ n ≤ 10^18) — the prediction on the number of people who will buy the game.


-----Output-----

Output one integer showing how many numbers from 1 to n are not divisible by any number from 2 to 10.


-----Examples-----
Input
12

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Penelope is part of the admin team of the newly built supercomputer. Her job is to assign workstations to the researchers who come here to run their computations at the supercomputer. 

Penelope is very lazy and hates unlocking machines for the arriving researchers. She can unlock the machines remotely from her desk, but does not feel that this menial task matches her qualifications. Should she decide to ignore the security guidelines she could simply ask the researchers not to lock their workstations when they leave, and then assign new researchers to workstations that are not used any more but that are still unlocked. That way, she only needs to unlock each workstation for the first researcher using it, which would be a huge improvement for Penelope.

Unfortunately, unused workstations lock themselves automatically if they are unused for more than $m$ minutes. After a workstation has locked itself, Penelope has to unlock it again for the next researcher using it. Given the exact schedule of arriving and leaving researchers, can you tell Penelope how many unlockings she may save by asking the researchers not to lock their workstations when they leave and assigning arriving researchers to workstations in an optimal way? You may assume that there are always enough workstations available.

-----Input-----
The input consists of:
 - one line with two integers $n$ ($1 \leq n \leq 300000$), the number of researchers, and $m$ ($1 \leq m \leq 10^8$), the number of minutes of inactivity after which a workstation locks itself;
 - $n$ lines each with two integers $a$ and $s$ ($1 \leq a, s \leq 10^8$), representing a researcher that arrives after $a$ minutes and stays for exactly $s$ minutes.

-----Output-----
Output the maximum number of unlockings Penelope may save herself.

-----Examples-----
Sample Input:
3 5
1 5
6 3
14 6
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ people in a row. The height of the $i$-th person is $a_i$. You can choose any subset of these people and try to arrange them into a balanced circle.

A balanced circle is such an order of people that the difference between heights of any adjacent people is no more than $1$. For example, let heights of chosen people be $[a_{i_1}, a_{i_2}, \dots, a_{i_k}]$, where $k$ is the number of people you choose. Then the condition $|a_{i_j} - a_{i_{j + 1}}| \le 1$ should be satisfied for all $j$ from $1$ to $k-1$ and the condition $|a_{i_1} - a_{i_k}| \le 1$ should be also satisfied. $|x|$ means the absolute value of $x$. It is obvious that the circle consisting of one person is balanced.

Your task is to choose the maximum number of people and construct a balanced circle consisting of all chosen people. It is obvious that the circle consisting of one person is balanced so the answer always exists.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of people.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the height of the $i$-th person.


-----Output-----

In the first line of the output print $k$ — the number of people in the maximum balanced circle.

In the second line print $k$ integers $res_1, res_2, \dots, res_k$, where $res_j$ is the height of the $j$-th person in the maximum balanced circle. The condition $|res_{j} - res_{j + 1}| \le 1$ should be satisfied for all $j$ from $1$ to $k-1$ and the condition $|res_{1} - res_{k}| \le 1$ should be also satisfied.


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

Output
5
2 1 1 2 3

Input
5
3 7 5 1 5

Output
2
5 5 

Input
3
5 1 4

Output
2
4 5 

Input
7
2 2 3 2 1 2 2

Output
7
1 2 2 2 2 3 2

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