vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
IIST is thinking of acquiring some land nearby to build its new state of the art labs. The land it has chosen incidentaly has some abandoned college buildings which IIST wants to use. The administration decide the value of the building based on the amount of work that has to be done to get it in shape (lower amount of work, higher value). The security experts want to tear down some of the buildings and use the bricks to build a boundary wall. 

The director has chosen you to write a program which determines the buildings which needs to be demolished to maximise the value while fulfilling the above criterion. 

Input Format: 

The first line contains the number of test cases, T.

The next T cases contains information about hypothetical plots.

Each test case starts with a single integer n, 2 ≤ n ≤ 15, the number of abandoned buildings in the plot. The buildings are identified by consecutive integers 1 to n. Each of the subsequent lines contains 4 integers x_i , y_i , v_i , l_i that describe a single building. (x_i, y_i) is the position of the building in the plane, v_i is its value, and l_i is the length of boundary wall that can be built using the bricks from the building. v_i and l_i are between 0 and 10,000.

Output Format:

For each test case, compute a subset of the buildings such that, using the bricks from the buildings from that subset, the remaining buildings can be enclosed in a single boundary. Find the subset with a minimum value. If more than one such minimum-value subset exists, choose one with the smallest number of buildings. 

Display, as shown below, the identity of each building to be demolished, and the length of the excess boundary (accurate to two fractional digits).

Sample Input:  

2

6

0 0 8 3

1 4 3 2

2 1 7 1

4 1 2 3

3 5 4 6

2 3 9 8

3

3 0 10 2

5 5 20 25

7 -3 30 32

Sample Output: 

2 4 5

3.16

2

15.00

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Quido has lunch in Hugo’s restaurant every day. He likes the restaurant because all of its prices are expressed as integers, and for each possible price (i.e. $$1$, $$2$, $$3$, etc.) there is at least one beverage and at least one main dish on the menu. Every day there are three entries printed on Quido’s lunch bill: the beverage price, the main dish price, and the total price. Hugo knows of Quido’s interest in computational problems and he offered Quido a free dessert each time his lunch bill meets the following three constraints:
 - the bill is not identical to any of Quido’s previous bills,
 - the price of the beverage is less than the price of the main dish, and
 - the prices listed on the bill cannot mutually use the same digit. In essence, any digit which occurs in any of the entries (beverage, main dish, total) must be different from any of the digits of the other two entries.

Quido is on a budget and he pays the same price for his lunch every day. How many times can he have a free dessert?

-----Input-----
The input consists of a single line with one integer representing the price $P$ which Quido pays for each lunch. The value of $P$ is positive and less than $10^{18}$.

-----Output-----
Output the maximum number of times Quido can have a free dessert at Hugo’s restaurant, provided that the price of his lunch is always $P$. Next, the possible bills which result in a free dessert are listed in ascending order with respect to the beverage price. Each bill consists of the price of the beverage followed by the price of the main dish. For simplicity, the value $P$, which is always the same, is not included in the bill.

If there are more than $5000$ possible bills, then output only the first $5000$ bills (but still report the total number of possible bills before the list of bills).

-----Examples-----
Sample Input 1:
37
Sample Output 1:
4
8 29
9 28
11 26
15 22

Sample Input 2:
30014
Sample Output 2:
7
85 29929
88 29926
785 29229
788 29226
7785 22229
7788 22226
7789 22225

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Stepan had a favorite string s which consisted of the lowercase letters of the Latin alphabet. 

After graduation, he decided to remember it, but it was a long time ago, so he can't now remember it. But Stepan remembers some information about the string, namely the sequence of integers c_1, c_2, ..., c_{n}, where n equals the length of the string s, and c_{i} equals the number of substrings in the string s with the length i, consisting of the same letters. The substring is a sequence of consecutive characters in the string s.

For example, if the Stepan's favorite string is equal to "tttesst", the sequence c looks like: c = [7, 3, 1, 0, 0, 0, 0].

Stepan asks you to help to repair his favorite string s according to the given sequence c_1, c_2, ..., c_{n}. 


-----Input-----

The first line contains the integer n (1 ≤ n ≤ 2000) — the length of the Stepan's favorite string.

The second line contains the sequence of integers c_1, c_2, ..., c_{n} (0 ≤ c_{i} ≤ 2000), where c_{i} equals the number of substrings of the string s with the length i, consisting of the same letters.

It is guaranteed that the input data is such that the answer always exists.


-----Output-----

Print the repaired Stepan's favorite string. If there are several answers, it is allowed to print any of them. The string should contain only lowercase letters of the English alphabet. 


-----Examples-----
Input
6
6 3 1 0 0 0

Output
kkrrrq
Input
4
4 0 0 0

Output
abcd



-----Note-----

In the first test Stepan's favorite string, for example, can be the string "kkrrrq", because it contains 6 substrings with the length 1, consisting of identical letters (they begin in positions 1, 2, 3, 4, 5 and 6), 3 substrings with the length 2, consisting of identical letters (they begin in positions 1, 3 and 4), and 1 substring with the length 3, consisting of identical letters (it begins in the position 3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a binary tree whose leaves are assigned integer weights. Such a tree is called balanced if, for every non-leaf node, the sum of the weights in its left subtree is equal to that in the right subtree. For instance, the tree in the following figure is balanced.

<image>
Figure I.1. A balanced tree


A balanced tree is said to be hidden in a sequence A, if the integers obtained by listing the weights of all leaves of the tree from left to right form a subsequence of A. Here, a subsequence is a sequence that can be derived by deleting zero or more elements from the original sequence without changing the order of the remaining elements.

For instance, the balanced tree in the figure above is hidden in the sequence 3 4 1 3 1 2 4 4 6, because 4 1 1 2 4 4 is a subsequence of it.

Now, your task is to find, in a given sequence of integers, the balanced tree with the largest number of leaves hidden in it. In fact, the tree shown in Figure I.1 has the largest number of leaves among the balanced trees hidden in the sequence mentioned above.



Input

The input consists of multiple datasets. Each dataset represents a sequence A of integers in the format


N
A1 A2 . . . AN


where 1 ≤ N ≤ 1000 and 1 ≤ Ai ≤ 500 for 1 ≤ i ≤ N. N is the length of the input sequence, and Ai is the i-th element of the sequence.

The input ends with a line consisting of a single zero. The number of datasets does not exceed 50.

Output

For each dataset, find the balanced tree with the largest number of leaves among those hidden in A, and output, in a line, the number of its leaves.

Example

Input

9
3 4 1 3 1 2 4 4 6
4
3 12 6 3
10
10 9 8 7 6 5 4 3 2 1
11
10 9 8 7 6 5 4 3 2 1 1
8
1 1 1 1 1 1 1 1
0


Output

6
2
1
5
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Kitahara Haruki's Gift

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kitahara Haruki has bought *n* apples for Touma Kazusa and Ogiso Setsuna. Now he wants to divide all the apples between the friends.

Each apple weights 100 grams or 200 grams. Of course Kitahara Haruki doesn't want to offend any of his friend. Therefore the total weight of the apples given to Touma Kazusa must be equal to the total weight of the apples given to Ogiso Setsuna.

But unfortunately Kitahara Haruki doesn't have a knife right now, so he cannot split any apple into some parts. Please, tell him: is it possible to divide all the apples in a fair way between his friends?

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=100) — the number of apples. The second line contains *n* integers *w*1,<=*w*2,<=...,<=*w**n* (*w**i*<==<=100 or *w**i*<==<=200), where *w**i* is the weight of the *i*-th apple.

Output Specification:
In a single line print "YES" (without the quotes) if it is possible to divide all the apples between his friends. Otherwise print "NO" (without the quotes).

Demo Input:
['3\n100 200 100\n', '4\n100 100 100 200\n']

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

Note:
In the first test sample Kitahara Haruki can give the first and the last apple to Ogiso Setsuna and the middle apple to Touma Kazusa.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The fight for the best number in the globe is going to finally come to an end.The top two contenders for the best number are number 2 and number 3.It's the final the entire world was waiting for. Expectorates from all across the globe came to witness the breath taking finals.

The finals began in an astonishing way.A common problem was set for both of them which included both these number.The problem goes like this.

Given a binary string (that is a string consisting of only 0 and 1). They were supposed to perform two types of query on the string.

Type 0: Given two indices l and r.Print the value of the binary string from l to r modulo 3.

Type 1: Given an index l flip the value of that index if and only if the value at that index is 0.

The problem proved to be a really tough one for both of them.Hours passed by but neither of them could solve the problem.So both of them wants you to solve this problem and then you get the right to choose the best number in the globe.

Input:

The first line contains N denoting the length of the binary string .The second line contains the N length binary string.Third line contains the integer Q indicating the number of queries to perform.This is followed up by Q lines where each line contains a query.

Output:

For each query of Type 0 print the value modulo 3.

Constraints:

1 ≤ N ≤10^5

1 ≤ Q ≤ 10^5

0 ≤ l ≤ r < N

SAMPLE INPUT
5
10010
6
0 2 4
0 2 3
1 1
0 0 4
1 1
0 0 3

SAMPLE OUTPUT
2
1
2
1

Explanation

Query 1 : This is of type 0. The binary string is 010 which is equal to 2 and 2%3=2. So answer is 2.

Query 2 : This is of type 0. The binary string is 01 which is equal to 1 ( (2^1) * 0 +(2^0) * 1 ) =0 + 1 =1) and 1%3=1. So answer is 1.

Query 3 : This is of type 1. The value at index 1 is 0 so we flip it .The new string is 11010.

Query 4 : This is of type 0. The binary string is 11010 ( (2^0) * 0 +(2^1) * 1 +(2^2) * 0 +(2^3) * 1 +(2^4) * 1 = 2 + 8 +16 =26 ) which is equal to 26 and 26%3=2. So answer is 2.

Query 5 :  This is of type 1. The value at index 1 is 1 so we do nothing .The new string is 11010.

Query 6 :  This is of type 0. The binary string is 1101 ( (2^0) * 1 +(2^1) * 0 +(2^2) * 1 +(2^3) * 1 = 1 + 4+ 8  =13 ) which is equal to 13 and 13%3=1. So answer is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
ACM NIT Surat has given Vinay, Minesweeper Master title for solving that problem in Codejam. In solving that Vinay has given 10 wrong submissions. Now anyone with fewer wrong submissions than him gets the title. And the first person with no wrong submissions retains title forever.

In the problem, 'Minesweeper Master', it is asked that for a given input(number of rows, number of columns, number of mines), the user should design a layout of minesweeper game so that positions of mines are denoted by '*', empty blocks are denoted by '.' and the trick is that you should win the game in just one click and the position of the click is to be denoted by 'c'. If it it not possible to win in one step, then print out Impossible.

Ex:
Input :  

10 10 82

Output :  

**********  
**********  
**********  
****....**  
***.....**  
***.c...**  
***....***  
**********  
**********  
**********

The rules of the game Minesweeper are like this.. There is a grid layout with X*Y identical cells. You may click on any cell to reveal it. If the revealed cell contains a mine, then the game is over, and you lose. Otherwise, the revealed cell will contain a digit between 0 and 8, inclusive, which corresponds to the number of neighbouring cells that contain mines. Two cells are neighbours if they share a corner or an edge. Additionally, if the revealed cell contains a 0, then all of the neighbours of the revealed cell are automatically revealed as well.

Now, Hitesh is trying for the title. He wants to get it with no wrong submissions. He made few layouts on a paper and finding out which positions to click on to win the game in one move. But he finds it difficult on how the layout changes in after the click at particular position. He asks you a well known Minesweeper player to help him how it changes.
Input:
First line of input has T, no. of test cases.
First line of every test case has two numbers X , Y denoting number of rows and columns in the layout Hitesh has prepared.
Next X lines consists of Y characters.
''* denotes position of mine.
'.' denotes empty block.
'c' denotes the block, Hitesh would like to click on.
There will be only one 'c' for each test case.

Output:
Print out the layout how would it appear after clicking on the block containing 'c'. Print output of each test case one below the other.

Constraints:
1 ≤ t ≤ 1000
1 ≤ x ≤ 100
1 ≤ y ≤ 100  

Problem Setter : Vinay Kumar

SAMPLE INPUT
3
3 3
***
***
**c
3 3
**c
***
***
5 10
.*********
**...*****
*..c.*****
**...**..*
*..****..*

SAMPLE OUTPUT
***
***
**3
**3
***
***
.*********
**435*****
*.203*****
**225**..*
*..****..*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Eugene has to do his homework. But today, he is feeling very lazy and wants to you do his homework. His homework has the following given maths problem.
You are given three integers: A, N, M. You write the number A appended to itself N times in a row. Let's call the resulting big number X. For example, if A = 120, N = 3, then X will be 120120120. Find out the value of X modulo M.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follow.
Each test case is described in one line containing three integers: A, N and M as described in the problem statement.

-----Output-----
For each test case, output a single line containing an integer denoting the value of X modulo M.

-----Constraints-----
- 1 ≤ T ≤ 105
- 0 ≤ A ≤ 109
- 1 ≤ N ≤ 1012
- 2 ≤ M ≤ 109

-----Subtasks-----
Subtask #1 (15 points):
- 0 ≤ A ≤ 100
- 1 ≤ N ≤ 105

Subtask #2 (25 points):
- 1 ≤ N ≤ 109

Subtask #3 (60 points):
- Original constraints

-----Example-----
Input:
2
12 2 17
523 3 11

Output:
5
6

-----Explanation-----
Example 1: As A = 12, N = 2, X = 1212, 1212 modulo 17 = 5
Example 2. As A = 523, N = 3, X = 523523523, 523523523 modulo 11 = 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Phoenix loves beautiful arrays. An array is beautiful if all its subarrays of length $k$ have the same sum. A subarray of an array is any sequence of consecutive elements.

Phoenix currently has an array $a$ of length $n$. He wants to insert some number of integers, possibly zero, into his array such that it becomes beautiful. The inserted integers must be between $1$ and $n$ inclusive. Integers may be inserted anywhere (even before the first or after the last element), and he is not trying to minimize the number of inserted integers.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 50$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 100$).

The second line of each test case contains $n$ space-separated integers ($1 \le a_i \le n$) — the array that Phoenix currently has. This array may or may not be already beautiful.


-----Output-----

For each test case, if it is impossible to create a beautiful array, print -1. Otherwise, print two lines.

The first line should contain the length of the beautiful array $m$ ($n \le m \le 10^4$). You don't need to minimize $m$.

The second line should contain $m$ space-separated integers ($1 \le b_i \le n$) — a beautiful array that Phoenix can obtain after inserting some, possibly zero, integers into his array $a$. You may print integers that weren't originally in array $a$.

If there are multiple solutions, print any. It's guaranteed that if we can make array $a$ beautiful, we can always make it with resulting length no more than $10^4$.


-----Example-----
Input
4
4 2
1 2 2 1
4 3
1 2 2 1
3 2
1 2 3
4 4
4 3 4 2

Output
5
1 2 1 2 1
4
1 2 2 1
-1
7
4 3 2 1 4 3 2


-----Note-----

In the first test case, we can make array $a$ beautiful by inserting the integer $1$ at index $3$ (in between the two existing $2$s). Now, all subarrays of length $k=2$ have the same sum $3$. There exists many other possible solutions, for example:   $2, 1, 2, 1, 2, 1$  $1, 2, 1, 2, 1, 2$ 

In the second test case, the array is already beautiful: all subarrays of length $k=3$ have the same sum $5$.

In the third test case, it can be shown that we cannot insert numbers to make array $a$ beautiful.

In the fourth test case, the array $b$ shown is beautiful and all subarrays of length $k=4$ have the same sum $10$. There exist other solutions also.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As we all know Barney's job is "PLEASE" and he has not much to do at work. That's why he started playing "cups and key". In this game there are three identical cups arranged in a line from left to right. Initially key to Barney's heart is under the middle cup. [Image] 

Then at one turn Barney swaps the cup in the middle with any of other two cups randomly (he choses each with equal probability), so the chosen cup becomes the middle one. Game lasts n turns and Barney independently choses a cup to swap with the middle one within each turn, and the key always remains in the cup it was at the start.

After n-th turn Barney asks a girl to guess which cup contains the key. The girl points to the middle one but Barney was distracted while making turns and doesn't know if the key is under the middle cup. That's why he asked you to tell him the probability that girl guessed right.

Number n of game turns can be extremely large, that's why Barney did not give it to you. Instead he gave you an array a_1, a_2, ..., a_{k} such that  $n = \prod_{i = 1}^{k} a_{i}$ 

in other words, n is multiplication of all elements of the given array.

Because of precision difficulties, Barney asked you to tell him the answer as an irreducible fraction. In other words you need to find it as a fraction p / q such that $\operatorname{gcd}(p, q) = 1$, where $gcd$ is the greatest common divisor. Since p and q can be extremely large, you only need to find the remainders of dividing each of them by 10^9 + 7.

Please note that we want $gcd$ of p and q to be 1, not $gcd$ of their remainders after dividing by 10^9 + 7.


-----Input-----

The first line of input contains a single integer k (1 ≤ k ≤ 10^5) — the number of elements in array Barney gave you.

The second line contains k integers a_1, a_2, ..., a_{k} (1 ≤ a_{i} ≤ 10^18) — the elements of the array.


-----Output-----

In the only line of output print a single string x / y where x is the remainder of dividing p by 10^9 + 7 and y is the remainder of dividing q by 10^9 + 7.


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

Output
1/2

Input
3
1 1 1

Output
0/1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Farmer Feb has three fields with potatoes planted in them. He harvested x potatoes from the first field, y potatoes from the second field and is yet to harvest potatoes from the third field. Feb is very superstitious and believes that if the sum of potatoes he harvests from the three fields is a prime number (http://en.wikipedia.org/wiki/Prime_number), he'll make a huge profit. Please help him by calculating for him the minimum number of potatoes that if harvested from the third field will make the sum of potatoes prime. At least one potato should be harvested from the third field.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. Each of the next T lines contain 2 integers separated by single space: x and y.

-----Output-----
For each test case, output a single line containing the answer.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ x ≤ 1000
- 1 ≤ y ≤ 1000

-----Example-----
Input:
2
1 3
4 3

Output:
1
4

-----Explanation-----

In example case 1: the farmer harvested a potato from the first field and 3 potatoes from the second field. The sum is 4. If he is able to harvest a potato from the third field, that will make the sum 5, which is prime. Hence the answer is 1(he needs one more potato to make the sum of harvested potatoes prime.)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sentence in the form of a string in uppercase, convert it into its equivalent mobile numeric keypad sequence. Please note there might be spaces in between the words in a sentence and we can print spaces by pressing 0.
 
Example 1:
Input:
S = "GFG"
Output: 43334
Explanation: For 'G' press '4' one time.
For 'F' press '3' three times.
Example 2:
Input:
S = "HEY U"
Output: 4433999088
Explanation: For 'H' press '4' two times.
For 'E' press '3' two times. For 'Y' press '9' 
three times. For white space press '0' one time.
For 'U' press '8' two times.
 
Your Task:  
You dont need to read input or print anything. Complete the function printSequence() which takes a string as input parameter and returns its equivalent mobile numeric keypad sequence as a string.
 
Expected Time Complexity: O(Length of String)
Expected Auxiliary Space: O(Length of String)
 
Constraints:
1 <= Length of String <= 10^{5}
Characters of string can be empty space or capital alphabets.

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