vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Each day in Berland consists of $n$ hours. Polycarp likes time management. That's why he has a fixed schedule for each day — it is a sequence $a_1, a_2, \dots, a_n$ (each $a_i$ is either $0$ or $1$), where $a_i=0$ if Polycarp works during the $i$-th hour of the day and $a_i=1$ if Polycarp rests during the $i$-th hour of the day.

Days go one after another endlessly and Polycarp uses the same schedule for each day.

What is the maximal number of continuous hours during which Polycarp rests? It is guaranteed that there is at least one working hour in a day.


-----Input-----

The first line contains $n$ ($1 \le n \le 2\cdot10^5$) — number of hours per day.

The second line contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1$), where $a_i=0$ if the $i$-th hour in a day is working and $a_i=1$ if the $i$-th hour is resting. It is guaranteed that $a_i=0$ for at least one $i$.


-----Output-----

Print the maximal number of continuous hours during which Polycarp rests. Remember that you should consider that days go one after another endlessly and Polycarp uses the same schedule for each day.


-----Examples-----
Input
5
1 0 1 0 1

Output
2

Input
6
0 1 0 1 1 0

Output
2

Input
7
1 0 1 1 1 0 1

Output
3

Input
3
0 0 0

Output
0



-----Note-----

In the first example, the maximal rest starts in last hour and goes to the first hour of the next day.

In the second example, Polycarp has maximal rest from the $4$-th to the $5$-th hour.

In the third example, Polycarp has maximal rest from the $3$-rd to the $5$-th hour.

In the fourth example, Polycarp has no rest at all.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has found a piece of paper with an array written on it. The array consists of n integers a_1, a_2, ..., a_{n}. Vasya noticed that the following condition holds for the array a_{i} ≤ a_{i} + 1 ≤ 2·a_{i} for any positive integer i (i < n).

Vasya wants to add either a "+" or a "-" before each number of array. Thus, Vasya will get an expression consisting of n summands. The value of the resulting expression is the sum of all its elements. The task is to add signs "+" and "-" before each number so that the value of expression s meets the limits 0 ≤ s ≤ a_1. Print a sequence of signs "+" and "-", satisfying the given limits. It is guaranteed that the solution for the problem exists.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the size of the array. The second line contains space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9) — the original array. 

It is guaranteed that the condition a_{i} ≤ a_{i} + 1 ≤ 2·a_{i} fulfills for any positive integer i (i < n).


-----Output-----

In a single line print the sequence of n characters "+" and "-", where the i-th character is the sign that is placed in front of number a_{i}. The value of the resulting expression s must fit into the limits 0 ≤ s ≤ a_1. If there are multiple solutions, you are allowed to print any of them.


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

Output
+++-
Input
3
3 3 5

Output
++-

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi, who is A years old, is riding a Ferris wheel.
It costs B yen (B is an even number) to ride the Ferris wheel if you are 13 years old or older, but children between 6 and 12 years old (inclusive) can ride it for half the cost, and children who are 5 years old or younger are free of charge. (Yen is the currency of Japan.)
Find the cost of the Ferris wheel for Takahashi.

-----Constraints-----
 - 0 ≤ A ≤ 100
 - 2 ≤ B ≤ 1000
 - B is an even number.

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Print the cost of the Ferris wheel for Takahashi.

-----Sample Input-----
30 100

-----Sample Output-----
100

Takahashi is 30 years old now, and the cost of the Ferris wheel is 100 yen.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A hostel has N rooms in a straight line. It has to accommodate X people. Unfortunately, out of these X people, Y of them are infected with chickenpox. Due to safety norms, the following precaution must be taken:

No person should occupy a room directly adjacent to a room occupied by a chickenpox-infected person. In particular, two chickenpox-infected people cannot occupy adjacent rooms.

For example, if room 4 has a chickenpox-infected person, then nobody should occupy rooms 3 and 5. Similarly, if room 1 has a chickenpox-infected person then nobody should occupy room 2. 

What's the minimum value of N for which all the people can be accommodated in the hostel, following the above condition?

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

- The first line of input contains a single integer T — the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains two integers X and Y — the total number of people and the number of chickenpox-infected people.

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

For each test case, output on a new line a single integer — the minimum value of N for which all the people can be accommodated in the hostel.

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

$1 ≤ T ≤ 200$
$1 ≤ X ≤ 1000$
$0 ≤ Y ≤ X$

----- Sample Input 1 ------ 
3
4 0
5 3
3 3

----- Sample Output 1 ------ 
4
8
5

----- explanation 1 ------ 
Note: Below, $C$ represents a room occupied by a chickenpox-infected person, $N$ represents a room occupied by an uninfected person, and $\_$ represents an empty room.

Test case $1$: One of the possible ways to accommodate the people in $4$ rooms is:

$N$ $N$ $N$ $N$ 

Test case $2$: One of the possible ways to accommodate the people in $8$ rooms is:

$C$ $\_$ $C$ $\_$ $N$ $N$ $\_$ $C$ 

Test case $3$: One of the possible ways to accommodate the people in $5$ rooms is:

$C$ $\_$ $C$ $\_$ $C$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Young Mirka is an amateur musician. She plays the multi-piano. $A$ multi-piano consists of an infinite number of multi-keys, denoted with integers that can be interpreted as the pitch. $A$ multi-composition (a composition written for a multi-piano) can be represented with a finite array of integers, where integers denote the order of multi-keys to press in order to play the multi-composition.

Young Mirka has heard a multi-composition on the multi-radio and now she wants to play it. Unfortunately, she cannot hear exactly which key was pressed, but instead she can hear whether the pressed multi-key was higher, lower or equal to the previously played key (a higher key is denoted with a larger number). Therefore she has decided to play the composition in the following way:
 - before playing, she will choose one non-negative integer $K$
 - in the beginning, she will play the correct multi-key (her multi-teacher told her which multi-key that is)
 - when she hears that the multi-key played in the multi-composition is higher than the previous multi-key played in the multi-composition, she will play the multi-key denoted with the integer larger than the multi-key she played previously by $K$
 - analogously, when she hears that the multi-key played in the multi-composition is lower than the previous multi-key played in the multi-composition, she will play the multi-key denoted with the integer smaller than the multi-key she played previously by $K$
 - when she hears that the multi-key played in the multi-composition is equal to the previous multi-key played in the multi-composition, she will repeat the multi-key she played previously

Notice that, when Mirka is playing, she does not compare the pitch of the keys she played to the pitch of the keys from the composition.

Help Mirka choose the integer $K$ in order to hit as many correct pitches as possible.

-----Input-----
The first line of input contains the integer $N$ ($2 \leq N \leq 10^6$), the number of multi-keys in the multi- composition on the multi-radio.

The second line of input contains $N$ integers $a_ i$ ($-10^9 \leq a_ i \leq 10^9$), the multi-keys played in the multi-composition.

-----Output-----
The first line of output must contain the maximum number of multi-keys that Mirka can play correctly. The second line of output must contain the non-negative number $K$ that Mirka must choose in order to hit as many correct pitches as possible. The number must be smaller than or equal to $2 \cdot 10^9$. The required number does not have to be unique, but will surely exist within the given constraints.

-----Examples-----
Sample Input:
5
1 2 0 3 1
Sample Output:
3
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
From the divine land of heaven came to earth a fruit known as Magic fruit.Unfortunately the fruit was found by two friends X and Y.
After lot of fighting,they came to the conclusion that they will share the fruit if and only if when they can divide it into two even weighing parts without wasting any part of fruit. Given weight of the fruit tell them if they can share it.

Input

The first (and the only) input line contains integer number w (1 ≤ w ≤ 100) — the weight of the magic fruit.

Output

Print YES, if the boys can divide the magic fruit into two parts, each of them weighing even number of kilos; and NO in the opposite case.

SAMPLE INPUT
8

SAMPLE OUTPUT
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Draw a rectangle which has a height of H cm and a width of W cm. Draw a 1-cm square by single '#'.

Constraints

* 1 ≤ H ≤ 300
* 1 ≤ W ≤ 300

Input

The input consists of multiple datasets. Each dataset consists of two integers H and W separated by a single space.

The input ends with two 0 (when both H and W are zero).

Output

For each dataset, print the rectangle made of H × W '#'.

Print a blank line after each dataset.

Example

Input

3 4
5 6
2 2
0 0


Output

####
####
####

######
######
######
######
######

##
##

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an infix expression in the form of string str. Convert this infix expression to postfix expression.
	Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.
	Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands.
	Note: The order of precedence is: ^ greater than * equals to / greater than + equals to -. 
Example 1:
Input: str = "a+b*(c^d-e)^(f+g*h)-i"
Output: abcd^e-fgh*+^*+i-
Explanation:
After converting the infix expression 
into postfix expression, the resultant 
expression will be abcd^e-fgh*+^*+i-
Example 2:
Input: str = "A*(B+C)/D"
Output: ABC+*D/
Explanation:
After converting the infix expression 
into postfix expression, the resultant 
expression will be ABC+*D/
 
Your Task:
This is a function problem. You only need to complete the function infixToPostfix() that takes a string(Infix Expression) as a parameter and returns a string(postfix expression). The printing is done automatically by the driver code.
Expected Time Complexity: O(|str|).
Expected Auxiliary Space: O(|str|).
Constraints:
1 ≤ |str| ≤ 10^{5}

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

Time Limit: 2 seconds

Memory Limit: 128 megabytes

Problem Description:
Last year Bob earned by selling memory sticks. During each of *n* days of his work one of the two following events took place: 
 -  A customer came to Bob and asked to sell him a 2*x* MB memory stick. If Bob had such a stick, he sold it and got 2*x* berllars. -  Bob won some programming competition and got a 2*x* MB memory stick as a prize. Bob could choose whether to present this memory stick to one of his friends, or keep it. 
Bob never kept more than one memory stick, as he feared to mix up their capacities, and deceive a customer unintentionally. It is also known that for each memory stick capacity there was at most one customer, who wanted to buy that memory stick. Now, knowing all the customers' demands and all the prizes won at programming competitions during the last *n* days, Bob wants to know, how much money he could have earned, if he had acted optimally.

Input Specification:
The first input line contains number *n* (1<=≤<=*n*<=≤<=5000) — amount of Bob's working days. The following *n* lines contain the description of the days. Line sell x stands for a day when a customer came to Bob to buy a 2*x* MB memory stick (0<=≤<=*x*<=≤<=2000). It's guaranteed that for each *x* there is not more than one line sell x. Line win x stands for a day when Bob won a 2*x* MB memory stick (0<=≤<=*x*<=≤<=2000).

Output Specification:
Output the maximum possible earnings for Bob in berllars, that he would have had if he had known all the events beforehand. Don't forget, please, that Bob can't keep more than one memory stick at a time.

Demo Input:
['7\nwin 10\nwin 5\nwin 3\nsell 5\nsell 3\nwin 10\nsell 10\n', '3\nwin 5\nsell 6\nsell 4\n']

Demo Output:
['1056\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The problem is simple. You are given a long sequence of integers $a_1, a_2, \ldots , a_ n$. Then you are given a query consisting of a start index $i$ and a subset of integers $B$. What is the longest consecutive subsequence of the given sequence that starts at position $i$ and contains only integers in $B$?

Simple, right?

-----Input-----
The first line of input contains a single integer $1 \leq n \leq 10^5$. The second line contains $n$ integers $a_1, \ldots , a_ n$. Each integer $a_ j$ lies between 0 and $2^{31}-1$.

The third line contains a single integer $q \geq 1$ indicating the number of queries to process. Then $q$ lines follow, each starting with two integers $1 \leq i \leq n$ and $1 \leq m \leq 10^5$, followed by $m$ distinct integers $b_1, \ldots , b_ m$. Each integer $b_ j$ lies between 0 and $2^{31}-1$.

Finally, you are guaranteed the sum of all values $m$ over all queries is at most $10^5$.

-----Output-----
For each query, output a single line with the length of the longest prefix of $a_ i, a_{i+1}, \ldots , a_ n$ that only contains integers from $B$.

-----Examples-----
Sample Input:
7
1 2 3 1 2 1 1
5
1 3 1 2 3
1 2 1 2
2 2 2 3
3 2 1 2
4 2 1 2
Sample Output:
7
2
2
0
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oh no!  You have stumbled upon a mysterious signal consisting of beeps of various lengths, and it is of utmost importance that you find out the secret message hidden in the beeps.  There are long and short beeps, the longer ones roughly three times as long as the shorter ones.  Hmm... that sounds familiar.

That's right: your job is to implement a decoder for the Morse alphabet.  Rather than dealing with actual beeps, we will use a common string encoding of Morse.  A long beep is represened by a dash (`-`) and a short beep by a dot (`.`).  A series of long and short beeps make up a letter, and letters are separated by spaces (` `).  Words are separated by double spaces.

You should implement the International Morse Alphabet.  You need to support letters a-z and digits 0-9 as follows:

    a .-      h ....    o ---     u ..-      1 .----     6 -....
    b -...    i ..      p .--.    v ...-     2 ..---     7 --...
    c -.-.    j .---    q --.-    w .--      3 ...--     8 ---..
    d -..     k -.-     r .-.     x -..-     4 ....-     9 ----.
    e .       l .-..    s ...     y -.--     5 .....     0 -----
    f ..-.    m --      t -       z --..
    g --.     n -.


## Examples

    .... . .-.. .-.. ---  .-- --- .-. .-.. -..   → "hello world"
    .---- ... -  .- -. -..  ..--- -. -..         → "1st and 2nd"

```if:python
A dictionnary `TOME` is preloaded for you, with the information above to convert morse code to letters.
```
```if:javascrip
An object `TOME` is preloaded for you, with the information above to convert morse code to letters.
```
```if:ruby
A Hashmap `$dict` is preloaded for you, with the information above to convert morse code to letters.
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hiking club "Up the hill" just returned from a walk. Now they are trying to remember which hills they've just walked through.

It is known that there were N stops, all on different integer heights between 1 and N kilometers (inclusive) above the sea level. On the first day they've traveled from the first stop to the second stop, on the second day they've traveled from the second to the third and so on, and on the last day they've traveled from the stop N - 1 to the stop N and successfully finished their expedition.

They are trying to find out which heights were their stops located at. They have an entry in a travel journal specifying how many days did they travel up the hill, and how many days did they walk down the hill.

Help them by suggesting some possible stop heights satisfying numbers from the travel journal.


-----Input-----

In the first line there is an integer non-negative number A denoting the number of days of climbing up the hill. Second line contains an integer non-negative number B — the number of days of walking down the hill (A + B + 1 = N, 1 ≤ N ≤ 100 000).


-----Output-----

Output N space-separated distinct integers from 1 to N inclusive, denoting possible heights of the stops in order of visiting.


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

Output
2 1 

Input
2
1
Output
1 3 4 2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A sequence of non-negative integers *a*1,<=*a*2,<=...,<=*a**n* of length *n* is called a wool sequence if and only if there exists two integers *l* and *r* (1<=≤<=*l*<=≤<=*r*<=≤<=*n*) such that . In other words each wool sequence contains a subsequence of consecutive elements with xor equal to 0.

The expression  means applying the operation of a bitwise xor to numbers *x* and *y*. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is marked as "^", in Pascal — as "xor".

In this problem you are asked to compute the number of sequences made of *n* integers from 0 to 2*m*<=-<=1 that are not a wool sequence. You should print this number modulo 1000000009 (109<=+<=9).

Input Specification:
The only line of input contains two space-separated integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=105).

Output Specification:
Print the required number of sequences modulo 1000000009 (109<=+<=9) on the only line of output.

Demo Input:
['3 2\n']

Demo Output:
['6\n']

Note:
Sequences of length 3 made of integers 0, 1, 2 and 3 that are not a wool sequence are (1, 3, 1), (1, 2, 1), (2, 1, 2), (2, 3, 2), (3, 1, 3) and (3, 2, 3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has N balls. Initially, an integer A_i is written on the i-th ball.
He would like to rewrite the integer on some balls so that there are at most K different integers written on the N balls.
Find the minimum number of balls that Takahashi needs to rewrite the integers on them.

-----Constraints-----
 - 1 \leq K \leq N \leq 200000
 - 1 \leq A_i \leq N
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 ... A_N

-----Output-----
Print the minimum number of balls that Takahashi needs to rewrite the integers on them.

-----Sample Input-----
5 2
1 1 2 2 5

-----Sample Output-----
1

For example, if we rewrite the integer on the fifth ball to 2, there are two different integers written on the balls: 1 and 2.
On the other hand, it is not possible to rewrite the integers on zero balls so that there are at most two different integers written on the balls, so we should print 1.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The programming competition season has already started and it's time to train for ICPC. Sereja coaches his teams for a number of year and he knows that to get ready for the training session it's not enough to prepare only problems and editorial. As the training sessions lasts for several hours, teams become hungry. Thus, Sereja orders a number of pizzas so they can eat right after the end of the competition.

Teams plan to train for *n* times during *n* consecutive days. During the training session Sereja orders exactly one pizza for each team that is present this day. He already knows that there will be *a**i* teams on the *i*-th day.

There are two types of discounts in Sereja's favourite pizzeria. The first discount works if one buys two pizzas at one day, while the second is a coupon that allows to buy one pizza during two consecutive days (two pizzas in total).

As Sereja orders really a lot of pizza at this place, he is the golden client and can use the unlimited number of discounts and coupons of any type at any days.

Sereja wants to order exactly *a**i* pizzas on the *i*-th day while using only discounts and coupons. Note, that he will never buy more pizzas than he need for this particular day. Help him determine, whether he can buy the proper amount of pizzas each day if he is allowed to use only coupons and discounts. Note, that it's also prohibited to have any active coupons after the end of the day *n*.

Input Specification:
The first line of input contains a single integer *n* (1<=≤<=*n*<=≤<=200<=000) — the number of training sessions.

The second line contains *n* integers *a*1, *a*2, ..., *a**n* (0<=≤<=*a**i*<=≤<=10<=000) — the number of teams that will be present on each of the days.

Output Specification:
If there is a way to order pizzas using only coupons and discounts and do not buy any extra pizzas on any of the days, then print "YES" (without quotes) in the only line of output. Otherwise, print "NO" (without quotes).

Demo Input:
['4\n1 2 1 2\n', '3\n1 0 1\n']

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

Note:
In the first sample, Sereja can use one coupon to buy one pizza on the first and the second days, one coupon to buy pizza on the second and the third days and one discount to buy pizzas on the fourth days. This is the only way to order pizzas for this sample.

In the second sample, Sereja can't use neither the coupon nor the discount without ordering an extra pizza. Note, that it's possible that there will be no teams attending the training sessions on some days.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have 3 equations with 3 unknowns x, y, and z and we are to solve for these unknowns.
Equations 4x -3y +z = -10, 2x +y +3z = 0, and -x +2y -5z = 17 will be passed in as an array of [[4, -3, 1, -10], [2, 1, 3, 0], [-1, 2, -5, 17]] and the result should be returned as an array like [1, 4, -2] (i.e. [x, y, z]).

Note: In C++ do not use new or malloc to allocate memory for the returned variable as allocated memory will not be freed in the Test Cases. Setting the variable as static will do.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a string of letters 'a' and 'b'. We want to perform some operations on it. On each step we choose one of substrings "ab" in the string and replace it with the string "bba". If we have no "ab" as a substring, our job is done. Print the minimum number of steps we should perform to make our job done modulo 10^9 + 7.

The string "ab" appears as a substring if there is a letter 'b' right after the letter 'a' somewhere in the string.


-----Input-----

The first line contains the initial string consisting of letters 'a' and 'b' only with length from 1 to 10^6.


-----Output-----

Print the minimum number of steps modulo 10^9 + 7.


-----Examples-----
Input
ab

Output
1

Input
aab

Output
3



-----Note-----

The first example: "ab"  →  "bba".

The second example: "aab"  →  "abba"  →  "bbaba"  →  "bbbbaa".

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