vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Alice likes all the numbers which are divisible by A. Bob does not like the numbers which are divisible by B and likes all the remaining numbers. Determine the smallest number greater than or equal to N which is liked by both Alice and Bob. Output -1 if no such number exists.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains three space-separated integers A, B and N — the parameters mentioned in the problem statment.

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

For each test case, output the smallest number ≥ N which is divisible by A and is not divisible by B. Output -1 if no such number exists.

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

$1 ≤ T ≤ 1000$
$1 ≤ A, B, N ≤ 10^{9}$

----- Sample Input 1 ------ 
3
5 2 11
4 3 24
7 7 100

----- Sample Output 1 ------ 
15
28
-1

----- explanation 1 ------ 
Test case $1$: $15$ is the smallest number $≥$ $11$ which is divisible by $5$ and is not divisible by $2$.

Test case $2$: $28$ is the smallest number $≥$ $24$ which is divisible by $4$ and is not divisible by $3$.

Test case $3$: There does not exist any number which is divisible by $A = 7$ and is not divisible by $B = 7$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi is taking exams on N subjects. The score on each subject will be an integer between 0 and K (inclusive).
He has already taken exams on N-1 subjects and scored A_i points on the i-th subject.
His goal is to achieve the average score of M points or above on the N subjects.
Print the minimum number of points Takahashi needs on the final subject to achieve his goal.
If the goal is unachievable, print -1 instead.

-----Constraints-----
 - 2 \leq N \leq 100
 - 1 \leq K \leq 100
 - 1 \leq M \leq K
 - 0 \leq A_i \leq K
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K M
A_1 A_2 ... A_{N-1}

-----Output-----
Print the minimum number of points required on the final subject, or -1.

-----Sample Input-----
5 10 7
8 10 3 6

-----Sample Output-----
8

If he scores 8 points on the final subject, his average score will be (8+10+3+6+8)/5 = 7 points, which meets the goal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n strings s_1, s_2, ..., s_{n} consisting of characters 0 and 1. m operations are performed, on each of them you concatenate two existing strings into a new one. On the i-th operation the concatenation s_{a}_{i}s_{b}_{i} is saved into a new string s_{n} + i (the operations are numbered starting from 1). After each operation you need to find the maximum positive integer k such that all possible strings consisting of 0 and 1 of length k (there are 2^{k} such strings) are substrings of the new string. If there is no such k, print 0.


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 100) — the number of strings. The next n lines contain strings s_1, s_2, ..., s_{n} (1 ≤ |s_{i}| ≤ 100), one per line. The total length of strings is not greater than 100.

The next line contains single integer m (1 ≤ m ≤ 100) — the number of operations. m lines follow, each of them contains two integers a_{i} abd b_{i} (1 ≤ a_{i}, b_{i} ≤ n + i - 1) — the number of strings that are concatenated to form s_{n} + i.


-----Output-----

Print m lines, each should contain one integer — the answer to the question after the corresponding operation.


-----Example-----
Input
5
01
10
101
11111
0
3
1 2
6 5
4 4

Output
1
2
0



-----Note-----

On the first operation, a new string "0110" is created. For k = 1 the two possible binary strings of length k are "0" and "1", they are substrings of the new string. For k = 2 and greater there exist strings of length k that do not appear in this string (for k = 2 such string is "00"). So the answer is 1.

On the second operation the string "01100" is created. Now all strings of length k = 2 are present.

On the third operation the string "1111111111" is created. There is no zero, so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Task:
Given an array arr of strings complete the function landPerimeter by calculating the total perimeter of all the islands. Each piece of land will be marked with 'X' while the water fields are represented as 'O'. Consider each tile being a perfect 1 x 1piece of land. Some examples for better visualization:

['XOOXO',
  'XOOXO',
  'OOOXO',
  'XXOXO',
  'OXOOO'] 

or 


should return:
"Total land perimeter: 24",

while


['XOOO',
  'XOXO',
  'XOXO',
  'OOXX',
  'OOOO']



should return: "Total land perimeter: 18"
Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Due to the increase in the number of students of Berland State University it was decided to equip a new computer room. You were given the task of buying mouses, and you have to spend as little as possible. After all, the country is in crisis!

The computers bought for the room were different. Some of them had only USB ports, some — only PS/2 ports, and some had both options.

You have found a price list of a certain computer shop. In it, for m mouses it is specified the cost and the type of the port that is required to plug the mouse in (USB or PS/2). Each mouse from the list can be bought at most once.

You want to buy some set of mouses from the given price list in such a way so that you maximize the number of computers equipped with mouses (it is not guaranteed that you will be able to equip all of the computers), and in case of equality of this value you want to minimize the total cost of mouses you will buy.

Input

The first line contains three integers a, b and c (0 ≤ a, b, c ≤ 105) — the number of computers that only have USB ports, the number of computers, that only have PS/2 ports, and the number of computers, that have both options, respectively.

The next line contains one integer m (0 ≤ m ≤ 3·105) — the number of mouses in the price list.

The next m lines each describe another mouse. The i-th line contains first integer vali (1 ≤ vali ≤ 109) — the cost of the i-th mouse, then the type of port (USB or PS/2) that is required to plug the mouse in.

Output

Output two integers separated by space — the number of equipped computers and the total cost of the mouses you will buy.

Example

Input

2 1 1
4
5 USB
6 PS/2
3 PS/2
7 PS/2


Output

3 14

Note

In the first example you can buy the first three mouses. This way you will equip one of the computers that has only a USB port with a USB mouse, and the two PS/2 mouses you will plug into the computer with PS/2 port and the computer with both ports.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Binod and his family live in Codingland. They have a festival called N-Halloween.
The festival is celebrated for N  consecutive days. On each day Binod gets some candies from his mother. He may or may not take them. On a given day ,  Binod will be sad if he collected candies on that day and he does not have at least X   candies remaining  from the candies he collected that day at the end of that day . His friend Pelu who is very fond of candies asks for X  candies from Binod on a day if Binod collects any candy on that day. He does so immediately after Binod collects them. Binod being a good friend never denies him.  

Given a list a   where ai   denotes the number of candies Binod may take on the ith   day and  Q  queries having a number X , find the maximum number of candies Binod can collect so that he won't be sad after the festival ends.
Input format: 

First-line contains two integers N and Q denoting the number of festival days and number of queries respectively.

The second line is the array whose ith   element is the maximum number of candies Binod may
collect on that day.

Each of the next Q lines contains the number X i.e the minimum number of candies Binod wants to have at the end of every day on which he collects any candy.
Output format: 

For every query output, a single integer denoting the max number of candies Binod may
collect (for the given X ) to be happy after the festival ends.
Constraints:  

1<=N,Q<=105  

1<=Q<=105  

0<=ai<=109  

0<=X<=109  

Sample Input : 

5 2

4 6 5 8 7

1

2

Sample Output : 

30

30

Sample Input:  

6 3 

20 10 12 3 30 5 

2 

6 

13 

Sample Output  

77 

62 

30 

Explanation: 

In the first query of sample input 1, Binod can collect the maximum number of given chocolates for a given day each day as after the end of every day Binod will have a number of collected
chocolates on that day greater than equal to 1 even after giving 1 chocolate to Pelu. So the
the answer is 4+6+5+8+7=30.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ consisting of $n$ integers $a_1, a_2, \dots, a_n$. You want to split it into exactly $k$ non-empty non-intersecting subsegments such that each subsegment has odd sum (i. e. for each subsegment, the sum of all elements that belong to this subsegment is odd). It is impossible to rearrange (shuffle) the elements of a given array. Each of the $n$ elements of the array $a$ must belong to exactly one of the $k$ subsegments.

Let's see some examples of dividing the array of length $5$ into $3$ subsegments (not necessarily with odd sums): $[1, 2, 3, 4, 5]$ is the initial array, then all possible ways to divide it into $3$ non-empty non-intersecting subsegments are described below:  $[1], [2], [3, 4, 5]$;  $[1], [2, 3], [4, 5]$;  $[1], [2, 3, 4], [5]$;  $[1, 2], [3], [4, 5]$;  $[1, 2], [3, 4], [5]$;  $[1, 2, 3], [4], [5]$. 

Of course, it can be impossible to divide the initial array into exactly $k$ subsegments in such a way that each of them will have odd sum of elements. In this case print "NO". Otherwise, print "YES" and any possible division of the array. See the output format for the detailed explanation.

You have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries. Then $q$ queries follow.

The first line of the query contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of elements in the array and the number of subsegments, respectively.

The second line of the query contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of $a$.

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each query, print the answer to it. If it is impossible to divide the initial array into exactly $k$ subsegments in such a way that each of them will have odd sum of elements, print "NO" in the first line. Otherwise, print "YES" in the first line and any possible division of the array in the second line. The division can be represented as $k$ integers $r_1$, $r_2$, ..., $r_k$ such that $1 \le r_1 < r_2 < \dots < r_k = n$, where $r_j$ is the right border of the $j$-th segment (the index of the last element that belongs to the $j$-th segment), so the array is divided into subsegments $[1; r_1], [r_1 + 1; r_2], [r_2 + 1, r_3], \dots, [r_{k - 1} + 1, n]$. Note that $r_k$ is always $n$ but you should print it anyway. 


-----Example-----
Input
3
5 3
7 18 3 14 1
5 4
1 2 3 4 5
6 2
1 2 8 4 10 2

Output
YES
1 3 5
NO
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $a$ and $b$.

In one move, you can choose some integer $k$ from $1$ to $10$ and add it to $a$ or subtract it from $a$. In other words, you choose an integer $k \in [1; 10]$ and perform $a := a + k$ or $a := a - k$. You may use different values of $k$ in different moves.

Your task is to find the minimum number of moves required to obtain $b$ from $a$.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$).


-----Output-----

For each test case, print the answer: the minimum number of moves required to obtain $b$ from $a$.


-----Example-----
Input
6
5 5
13 42
18 4
1337 420
123456789 1000000000
100500 9000

Output
0
3
2
92
87654322
9150



-----Note-----

In the first test case of the example, you don't need to do anything.

In the second test case of the example, the following sequence of moves can be applied: $13 \rightarrow 23 \rightarrow 32 \rightarrow 42$ (add $10$, add $9$, add $10$).

In the third test case of the example, the following sequence of moves can be applied: $18 \rightarrow 10 \rightarrow 4$ (subtract $8$, subtract $6$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya is preparing a problem for a local contest in his school. The problem is to find a longest increasing subsequence in a given permutation. A permutation of size n$n$ is a sequence of n$n$ numbers a1,…,an$a_1, \ldots, a_n$ such that every number from 1$1$ to n$n$ occurs in the sequence exactly once. An increasing subsequence of length k$k$ of the sequence a1,…,an$a_1, \ldots, a_n$ is a sequence of indices i1,…,ik$i_1, \ldots, i_k$ such that 1≤i1<…<ik≤n$1 \leq i_1 < \ldots < i_k \leq n$ and ai1<…<aik$a_{i_1} < \ldots < a_{i_k}$. A longest increasing subsequence is an increasing subsequences with the largest length. Note that in general there may be several longest increasing subsequences.
Petya had some tests prepared, but then lost the input part for some of them. He now has a test for a certain value of n$n$, and a sequence i1,…,ik$i_1, \ldots, i_k$ that is supposed to be a longest increasing subsequence. Petya now has to reconstruct a permutation of size n$n$ with this sequence being an answer. Petya doesn't want to take any risks, so he additionally wants this sequence to be the only longest increasing subsequence, that is, all other increasing subsequences have to have strictly smaller length. Help Petya determine if this is possible, and if so, construct any such permutation.

-----Input:-----
The first line contains an integer T$T$, denoting number of test cases.
The first line of every test case contains two integers n$n$ and k−$k-$  the size of the permutation and the length of the longest increasing subsequence (1≤k≤n≤105$1 \leq k \leq n \leq 10^5$).
The second line contains k$k$ integers i1,…,ik−$i_1, \ldots, i_k-$ the longest increasing subsequence (1≤i1<…<ik≤n$1 \leq i_1 < \ldots < i_k \leq n$).

-----Output:-----
If there is no permutation with the sequence i1,…,ik$i_1, \ldots, i_k$ being the only longest increasing subsequence, print NO . Otherwise, print YES on the first line, followed by n$n$ numbers describing any suitable permutation on the second line.

-----Constraints-----
- 1≤T≤10$1 \leq T \leq 10$
- 1≤k≤n≤105$1 \leq k \leq n \leq 10^5$ 
- 1≤i1<…<ik≤n$1 \leq i_1 < \ldots < i_k \leq n$ 

-----Sample Input:-----
2
3 2
1 2
2 1
1

-----Sample Output:-----
YES
2 3 1
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While walking in grand malls little Elsa likes to play a game she calls “Lava”. This is a simple game using the different colors of the floor tiles as markers for where it is safe to walk and where it is not. The rules of the game say that you’re allowed to walk on white tiles, but not on black tiles. The tiles are square.

Elsa typically plays this game together with her father. As he is an adult and (sometimes) can move over tiles that Elsa cannot, Elsa has decided that she is allowed to move in all directions while her father is only allowed to move along the $2$ axes of the floor tiles, and they are only allowed to take steps up to a certain length. This means in particular that Elsa can move to any tile within the radius of her step length (measured in the usual Euclidean distance).

The goal of this game is to get from store $A$ to store $B$ as quickly as possible. Both players move at the same time and they are not allowed to do the next move until they are both finished with the first move. As both the father and Elsa hate to lose, the best outcome is to end up with them getting to the finish at the same time. The father would not like to participate in a game where Elsa will lose, or a game where her father can be seen as trying to lose on purpose (Elsa always knows). A player who can’t reach the goal obviously loses.

-----Input-----
The fist line of the input is a line consisting of $2$ integers $A$ and $F$ indicating the maximum step length of Elsa and the maximum step length of the father respectively. The step lengths are given as multiples of a tile width.

 Then follows a line with $2$ integers $L$ and $W$ indicating the length and width of the map of their possible Lava game.

 Then follow $L$ lines each consisting of a string of length $W$, indicating the tiles of the map. Here ‘S’ denotes the start tile, ‘G’ denotes the goal tile, ‘W’ denotes a safe tile and ‘B’ denotes a lava tile.

-----Output-----
Output a line with the word “SUCCESS” if they both reach the goal at the same time, “GO FOR IT” if Elsa wins and “NO CHANCE” if the father would win. If neither Elsa nor her father is able to reach the goal, output “NO WAY”.

-----Limits-----
 - $1 \leq A \leq 1000$
 - $1 \leq F \leq 1000$
 - $1 \leq L \leq 1000$
 - $1 \leq W \leq 1000$
 - The number of ‘W’ tiles will be at most $1000$.
 - The map will only contain the characters ’S’, ’G’, ’W’ and ’B’ and there will only be one ’S’ character and one ’G’ character per map.

-----Examples-----
Sample Input:
2 3
4 4
WWWW
WSBB
WWWW
WBWG
Sample Output:
GO FOR IT

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Bear and Tower of Cubes

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Limak is a little polar bear. He plays by building towers from blocks. Every block is a cube with positive integer length of side. Limak has infinitely many blocks of each side length.

A block with side *a* has volume *a*3. A tower consisting of blocks with sides *a*1,<=*a*2,<=...,<=*a**k* has the total volume *a*13<=+<=*a*23<=+<=...<=+<=*a**k*3.

Limak is going to build a tower. First, he asks you to tell him a positive integer *X* — the required total volume of the tower. Then, Limak adds new blocks greedily, one by one. Each time he adds the biggest block such that the total volume doesn't exceed *X*.

Limak asks you to choose *X* not greater than *m*. Also, he wants to maximize the number of blocks in the tower at the end (however, he still behaves greedily). Secondarily, he wants to maximize *X*.

Can you help Limak? Find the maximum number of blocks his tower can have and the maximum *X*<=≤<=*m* that results this number of blocks.

Input Specification:
The only line of the input contains one integer *m* (1<=≤<=*m*<=≤<=1015), meaning that Limak wants you to choose *X* between 1 and *m*, inclusive.

Output Specification:
Print two integers — the maximum number of blocks in the tower and the maximum required total volume *X*, resulting in the maximum number of blocks.

Demo Input:
['48\n', '6\n']

Demo Output:
['9 42\n', '6 6\n']

Note:
In the first sample test, there will be 9 blocks if you choose *X* = 23 or *X* = 42. Limak wants to maximize *X* secondarily so you should choose 42.

In more detail, after choosing *X* = 42 the process of building a tower is:
 -  Limak takes a block with side 3 because it's the biggest block with volume not greater than 42. The remaining volume is 42 - 27 = 15. -  The second added block has side 2, so the remaining volume is 15 - 8 = 7. -  Finally, Limak adds 7 blocks with side 1, one by one. 
So, there are 9 blocks in the tower. The total volume is is 3<sup class="upper-index">3</sup> + 2<sup class="upper-index">3</sup> + 7·1<sup class="upper-index">3</sup> = 27 + 8 + 7 = 42.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The goal of this Kata is to return the greatest distance of index positions between matching number values in an array or 0 if there are no matching values.  

Example:
In an array with the values [0, 2, 1, 2, 4, 1] the greatest index distance is between the matching '1' values at index 2 and 5.  Executing greatestDistance against this array would return 3. (i.e. 5 - 2)  

Here's the previous example in test form:
```python
test.assert_equals(greatest_distance([0, 2, 1, 2, 4, 1]), 3)
```

This is based on a Kata I had completed only to realize I has misread the instructions.  I enjoyed solving the problem I thought it was asking me to complete so I thought I'd add a new Kata for others to enjoy.  There are no tricks in this one, good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number $n$, give the last digit of sum of all the prime numbers from 1 to $n$ inclusive.

-----Input:-----
- First line contains number of testcase $t$.
- Each testcase contains of a single line of input, number $n$. 

-----Output:-----
Last digit of sum of every prime number till n.

-----Constraints-----
- $1 \leq T \leq 10$
- $2 \leq N \leq 10^6$

-----Sample Input:-----
1
10

-----Sample Output:-----
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is never too late to play the fancy "Binary Cards" game!

There is an infinite amount of cards of positive and negative ranks that are used in the game. The absolute value of any card rank is a power of two, i.e. each card has a rank of either 2k or  - 2k for some integer k ≥ 0. There is an infinite amount of cards of any valid rank.

At the beginning of the game player forms his deck that is some multiset (possibly empty) of cards. It is allowed to pick any number of cards of any rank but the small deck is considered to be a skill indicator. Game consists of n rounds. In the i-th round jury tells the player an integer ai. After that the player is obligated to draw such a subset of his deck that the sum of ranks of the chosen cards is equal to ai (it is allowed to not draw any cards, in which case the sum is considered to be equal to zero). If player fails to do so, he loses and the game is over. Otherwise, player takes back all of his cards into his deck and the game proceeds to the next round. Player is considered a winner if he is able to draw the suitable set of cards in each of the rounds.

Somebody told you which numbers ai the jury is going to tell you in each round. Now you want to pick a deck consisting of the minimum number of cards that allows you to win the "Binary Cards" game.

Input

The first line of input contains an integer n (1 ≤ n ≤ 100 000), the number of rounds in the game.

The second line of input contains n integers a1, a2, ..., an ( - 100 000 ≤ ai ≤ 100 000), the numbers that jury is going to tell in each round.

Output

In the first line print the integer k (0 ≤ k ≤ 100 000), the minimum number of cards you have to pick in your deck in ordered to win the "Binary Cards".

In the second line print k integers b1, b2, ..., bk ( - 220 ≤ bi ≤ 220, |bi| is a power of two), the ranks of the cards in your deck. You may output ranks in any order. If there are several optimum decks, you are allowed to print any of them.

It is guaranteed that there exists a deck of minimum size satisfying all the requirements above.

Examples

Input

1
9


Output

2
1 8


Input

5
-1 3 0 4 7


Output

3
4 -1 4


Input

4
2 -2 14 18


Output

3
-2 2 16

Note

In the first sample there is the only round in the game, in which you may simply draw both your cards. Note that this sample test is the only one satisfying the first test group constraints.

In the second sample you may draw the only card  - 1 in the first round, cards 4 and  - 1 in the second round, nothing in the third round, the only card 4 in the fourth round and the whole deck in the fifth round.

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