vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
It is exam time! You have, of course, been spending too much time participating in various programming contests and have not done much studying. Now you have $N$ subjects to study for, but only a limited amount of time before the final exams. You have to decide how much time to allocate to studying each subject, so that your average grade over all $N$ subjects is maximized. 

As a seasoned programming contest competitor, you recognize immediately that you can determine the optimal allocation with a computer program. Of course, you have decided to ignore the amount of time you spend solving this problem (i.e. procrastinating).

You have a total of $T$ hours that you can split among different subjects. For each subject $i$, the expected grade with $t$ hours of studying is given by the function $f_ i(t) = a_ i t^2 + b_ i t + c_ i$, satisfying the following properties:
 - $f_ i(0) \geq 0$;
 - $f_ i(T) \leq 100$;
 - $a_ i < 0$;
 - $f_ i(t)$ is a non-decreasing function in the interval $[0,T]$.

You may allocate any fraction of an hour to a subject, not just whole hours. What is the maximum average grade you can obtain over all $n$ subjects?

-----Input-----
The first line of each input contains the integers $N$ ($1 \leq N \le 10$) and $T$ ($1 \leq T \le 240$) separated by a space. This is followed by $N$ lines, each containing the three parameters $a_ i$, $b_ i$, and $c_ i$ describing the function $f_ i(t)$. The three parameters are separated by a space, and are given as real numbers with $4$ decimal places. Their absolute values are no more than $100$.

-----Output-----
Output in a single line the maximum average grade you can obtain. Answers within $0.01$ of the correct answer will be accepted.

-----Examples-----
Sample Input:
2 96
-0.0080 1.5417 25.0000
-0.0080 1.5417 25.0000
Sample Output:
80.5696000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a number N, Cheffina challenges the chef to check the divisibility of all the permutation of N by 3. If any of the permutations is divisible by 3 then print 1 else print 0.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, two integers $N$. 

-----Output:-----
For each test case, output in a single line answer 1 or 0.

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

-----Sample Input:-----
2
18
308

-----Sample Output:-----
1
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write your program in Ruby which takes an un-indented Ruby code as string and outputs the indented Ruby code as string.

Input Format
A string which is un-indented Ruby code

Output Format
A string which is indented Ruby code

SAMPLE INPUT
class YabbaDabbaDoo
        def foo
        if foo == 42
        puts 'world hello'
          elsif foo == 24
          puts 'bk201'
        else
        puts 'congrats!'
          end
  end
end

SAMPLE OUTPUT
class YabbaDabbaDoo
 def foo
  if foo == 42
   puts 'world hello'
  elsif foo == 24
   puts 'bk201'
  else
   puts 'congrats!'
  end
 end
end

Explanation

Indentation is of 2 spaces.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a_1, a_2, \dots , a_n$. Array is good if for each pair of indexes $i < j$ the condition $j - a_j \ne i - a_i$ holds. Can you shuffle this array so that it becomes good? To shuffle an array means to reorder its elements arbitrarily (leaving the initial order is also an option).

For example, if $a = [1, 1, 3, 5]$, then shuffled arrays $[1, 3, 5, 1]$, $[3, 5, 1, 1]$ and $[5, 3, 1, 1]$ are good, but shuffled arrays $[3, 1, 5, 1]$, $[1, 1, 3, 5]$ and $[1, 1, 5, 3]$ aren't.

It's guaranteed that it's always possible to shuffle an array to meet this condition.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1 \le n \le 100$) — the length of array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le 100$).


-----Output-----

For each test case print the shuffled version of the array $a$ which is good.


-----Example-----
Input
3
1
7
4
1 1 3 5
6
3 2 1 5 6 4

Output
7
1 5 1 3
2 4 6 1 3 5

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dima's got a staircase that consists of *n* stairs. The first stair is at height *a*1, the second one is at *a*2, the last one is at *a**n* (1<=≤<=*a*1<=≤<=*a*2<=≤<=...<=≤<=*a**n*). 

Dima decided to play with the staircase, so he is throwing rectangular boxes at the staircase from above. The *i*-th box has width *w**i* and height *h**i*. Dima throws each box vertically down on the first *w**i* stairs of the staircase, that is, the box covers stairs with numbers 1,<=2,<=...,<=*w**i*. Each thrown box flies vertically down until at least one of the two following events happen:
 -  the bottom of the box touches the top of a stair; -  the bottom of the box touches the top of a box, thrown earlier. 
We only consider touching of the horizontal sides of stairs and boxes, at that touching with the corners isn't taken into consideration. Specifically, that implies that a box with width *w**i* cannot touch the stair number *w**i*<=+<=1.

You are given the description of the staircase and the sequence in which Dima threw the boxes at it. For each box, determine how high the bottom of the box after landing will be. Consider a box to fall after the previous one lands.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — the number of stairs in the staircase. The second line contains a non-decreasing sequence, consisting of *n* integers, *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109; *a**i*<=≤<=*a**i*<=+<=1).

The next line contains integer *m* (1<=≤<=*m*<=≤<=105) — the number of boxes. Each of the following *m* lines contains a pair of integers *w**i*,<=*h**i* (1<=≤<=*w**i*<=≤<=*n*; 1<=≤<=*h**i*<=≤<=109) — the size of the *i*-th thrown box.

The numbers in the lines are separated by spaces.

Output Specification:
Print *m* integers — for each box the height, where the bottom of the box will be after landing. Print the answers for the boxes in the order, in which the boxes are given in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Demo Input:
['5\n1 2 3 6 6\n4\n1 1\n3 1\n1 1\n4 3\n', '3\n1 2 3\n2\n1 1\n3 1\n', '1\n1\n5\n1 2\n1 10\n1 10\n1 10\n1 10\n']

Demo Output:
['1\n3\n4\n6\n', '1\n3\n', '1\n3\n13\n23\n33\n']

Note:
The first sample are shown on the picture.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Vasya has gotten interested in programming contests in TCMCF+++ rules. On the contest *n* problems were suggested and every problem had a cost — a certain integral number of points (perhaps, negative or even equal to zero). According to TCMCF+++ rules, only accepted problems can earn points and the overall number of points of a contestant was equal to the product of the costs of all the problems he/she had completed. If a person didn't solve anything, then he/she didn't even appear in final standings and wasn't considered as participant. Vasya understood that to get the maximal number of points it is not always useful to solve all the problems. Unfortunately, he understood it only after the contest was finished. Now he asks you to help him: find out what problems he had to solve to earn the maximal number of points.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=100) — the number of the suggested problems. The next line contains *n* space-separated integers *c**i* (<=-<=100<=≤<=*c**i*<=≤<=100) — the cost of the *i*-th task. The tasks' costs may coinсide.

Output Specification:
Print space-separated the costs of the problems that needed to be solved to get the maximal possible number of points. Do not forget, please, that it was necessary to solve at least one problem. If there are several solutions to that problem, print any of them.

Demo Input:
['5\n1 2 -3 3 3\n', '13\n100 100 100 100 100 100 100 100 100 100 100 100 100\n', '4\n-2 -2 -2 -2\n']

Demo Output:
['3 1 2 3 \n', '100 100 100 100 100 100 100 100 100 100 100 100 100 \n', '-2 -2 -2 -2 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two players A and B have a list of $n$ integers each. They both want to maximize the subtraction between their score and their opponent's score. 

In one turn, a player can either add to his score any element from his list (assuming his list is not empty), the element is removed from the list afterward. Or remove an element from his opponent's list (assuming his opponent's list is not empty).

Note, that in case there are equal elements in the list only one of them will be affected in the operations above. For example, if there are elements $\{1, 2, 2, 3\}$ in a list and you decided to choose $2$ for the next turn, only a single instance of $2$ will be deleted (and added to the score, if necessary). 

The player A starts the game and the game stops when both lists are empty. Find the difference between A's score and B's score at the end of the game, if both of the players are playing optimally.

Optimal play between two players means that both players choose the best possible strategy to achieve the best possible outcome for themselves. In this problem, it means that each player, each time makes a move, which maximizes the final difference between his score and his opponent's score, knowing that the opponent is doing the same.


-----Input-----

The first line of input contains an integer $n$ ($1 \le n \le 100\,000$) — the sizes of the list.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^6$), describing the list of the player A, who starts the game.

The third line contains $n$ integers $b_i$ ($1 \le b_i \le 10^6$), describing the list of the player B.


-----Output-----

Output the difference between A's score and B's score ($A-B$) if both of them are playing optimally.


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

Output
0
Input
3
100 100 100
100 100 100

Output
0
Input
2
2 1
5 6

Output
-3


-----Note-----

In the first example, the game could have gone as follows:   A removes $5$ from B's list.  B removes $4$ from A's list.  A takes his $1$.  B takes his $1$. 

Hence, A's score is $1$, B's score is $1$ and difference is $0$.

There is also another optimal way of playing:  A removes $5$ from B's list.  B removes $4$ from A's list.  A removes $1$ from B's list.  B removes $1$ from A's list. 

The difference in the scores is still $0$.

In the second example, irrespective of the moves the players make, they will end up with the same number of numbers added to their score, so the difference will be $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. G is one of the most excellent students in North River High School for Gifted Students. Despite having impressive performance in a programming competition and making it to the next round, he was not totally happy since his best friend did not get such a great achievement. In order to appease the poor girl, Mr. G has to deal with a very hard challenge: Buy her some ginger candies!

The road system in North River province consists of $N$ junctions and $M$ bidirectional roads. Junctions are numbered from $1$ to $N$, and roads are numbered from $1$ to $M$, inclusive. On the $i^{th}$ road, which connects two junctions $u_ i$ and $v_ i$, there is a shop in which Mr. G can buy $c_ i$ ginger candies. No two roads have the same number of candies. Mr. G wants to meet his friend at some junction, travel through several roads without visiting the same road twice, buy all candies on those roads, and finish at the same junction where he starts.

Using his humble knowledge in Physics, Mr. G calculates the amount of energy he needs to spend as follow: Let $L$ be the maximum number of candies he buys in one road, and $K$ be the number of roads he passes through. The amount of energy he needs to spend is $L^2+\alpha K$, where $\alpha $ is some constant he has already known.

Help him to satisfy his friend with the minimum amount of energy.

-----Input-----
 - The first line contains three integers $N$, $M$, $\alpha $, the number of junctions, the number of roads and the predefined constant Mr. G uses to calculate the amount of energy, respectively ($1 \leq N \leq 10^5$, $1 \leq M \leq 2 \times 10^5$, $1 \leq \alpha \leq 20$).
 - In the next $M$ lines, each contains three integers $u$, $v$, $c$ ($1 \leq u \leq N$, $1 \leq v \leq N$, $10^6 \leq c \leq 10^9$), meaning that there is a road connecting two junctions $u$ and $v$, which sells $c$ ginger candies.

It is guaranteed that all $c$ in the above $M$ lines are distinct.

-----Output-----
Write one integer denoting the minimum amount of energy Mr. G has to spend. If there is no route satisfying the condition, output Poor girl instead.

-----Examples-----
Sample Input 1:
7 7 10
1 2 1000000
2 3 2000000
3 4 3000000
4 5 4000000
5 6 5000000
6 7 6000000
7 1 7000000
Sample Output 1:
49000000000070

Sample Input 2:
6 6 7
1 3 1000000
3 5 3000000
5 1 5000000
2 4 2000000
4 6 4000000
6 2 6000000
Sample Output 2:
25000000000021

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A new school year is approaching, which also means students will be taking tests. 

The tests in this kata are to be graded in different ways. A certain number of points will be given for each correct answer and a certain number of points will be deducted for each incorrect answer. For ommitted answers, points will either be awarded, deducted, or no points will be given at all.

Return the number of points someone has scored on varying tests of different lengths.

The given parameters will be:

* An array containing a series of `0`s, `1`s, and `2`s, where `0` is a correct answer, `1` is an omitted answer, and `2` is an incorrect answer.
* The points awarded for correct answers
* The points awarded for omitted answers (note that this may be negative)
* The points **deducted** for incorrect answers (hint: this value has to be subtracted)


**Note:**
The input will always be valid (an array and three numbers)


## Examples

\#1:
```
[0, 0, 0, 0, 2, 1, 0], 2, 0, 1  -->  9
```
because:
* 5 correct answers: `5*2 = 10`
* 1 omitted answer: `1*0 = 0`
* 1 wrong answer: `1*1 = 1`

which is: `10 + 0 - 1 = 9`

\#2:
```
[0, 1, 0, 0, 2, 1, 0, 2, 2, 1], 3, -1, 2)  -->  3
```
because: `4*3 + 3*-1 - 3*2 = 3`

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

The input format is following:



n m q
a_1 a_2 ... a_q


Output Format

Print the number of connected part in one line.


Constraints

* n ≤ 10^{12}
* 7n is divisible by m.
* 1 ≤ q ≤ m ≤ 10^5
* 0 ≤ a_1 < a_2 < ... < a_q < m



Scoring

Subtask 1 [100 points]


* n ≤ 100000.

Subtask 2 [90 points]


* m is divisible by 7.
* a_{i + 1} - a_i = 1.

Subtask 3 [200 points]


* m is divisible by 7.

Subtask 4 [110 points]


* There are no additional constraints.



Sample Input 1


7 7 3
1 3 5


Sample Output 1


4


The calendar looks like this:


<image>

Sample Input 2


10 14 8
5 6 7 8 9 10 11 12


Sample Output 2


10


The calendar looks like this:


<image>

Output Format

Print the number of connected part in one line.


Constraints

* n ≤ 10^{12}
* 7n is divisible by m.
* 1 ≤ q ≤ m ≤ 10^5
* 0 ≤ a_1 < a_2 < ... < a_q < m



Scoring

Subtask 1 [100 points]


* n ≤ 100000.

Subtask 2 [90 points]


* m is divisible by 7.
* a_{i + 1} - a_i = 1.

Subtask 3 [200 points]


* m is divisible by 7.

Subtask 4 [110 points]


* There are no additional constraints.

Input Format

The input format is following:



n m q
a_1 a_2 ... a_q

Examples

Input

7 7 3
1 3 5


Output

4


Input

10 14 8
5 6 7 8 9 10 11 12


Output

10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A high school has a strange principal. On the first day, he has his students perform an odd opening day ceremony:

There are number of lockers "n" and number of students "n" in the school. The principal asks the first student to go to every locker and open it. Then he has the second student go to every second locker and close it. The third goes to every third locker and, if it is closed, he opens it, and if it is open, he closes it. The fourth student does this to every fourth locker, and so on. After the process is completed with the "n"th student, how many lockers are open?

The task is to write a function which gets any number as an input and returns the number of open lockers after last sudent complets his activity. So input of the function is just one number which shows number of lockers and number of students. For example if there are 1000 lockers and 1000 students in school then input is 1000 and function returns number of open lockers after 1000th student completes his action.

The given input is always an integer greater than or equal to zero that is why there is no need for validation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp plays "Game 23". Initially he has a number $n$ and his goal is to transform it to $m$. In one move, he can multiply $n$ by $2$ or multiply $n$ by $3$. He can perform any number of moves.

Print the number of moves needed to transform $n$ to $m$. Print -1 if it is impossible to do so.

It is easy to prove that any way to transform $n$ to $m$ contains the same number of moves (i.e. number of moves doesn't depend on the way of transformation).


-----Input-----

The only line of the input contains two integers $n$ and $m$ ($1 \le n \le m \le 5\cdot10^8$).


-----Output-----

Print the number of moves to transform $n$ to $m$, or -1 if there is no solution.


-----Examples-----
Input
120 51840

Output
7

Input
42 42

Output
0

Input
48 72

Output
-1



-----Note-----

In the first example, the possible sequence of moves is: $120 \rightarrow 240 \rightarrow 720 \rightarrow 1440 \rightarrow 4320 \rightarrow 12960 \rightarrow 25920 \rightarrow 51840.$ The are $7$ steps in total.

In the second example, no moves are needed. Thus, the answer is $0$.

In the third example, it is impossible to transform $48$ to $72$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob are playing a game. They are given an array $A$ of length $N$. The array consists of integers. They are building a sequence together. In the beginning, the sequence is empty. In one turn a player can remove a number from the left or right side of the array and append it to the sequence. The rule is that the sequence they are building must be strictly increasing. The winner is the player that makes the last move. Alice is playing first. Given the starting array, under the assumption that they both play optimally, who wins the game?


-----Input-----

The first line contains one integer $N$ ($1 \leq N \leq 2*10^5$) - the length of the array $A$.

The second line contains $N$ integers $A_1$, $A_2$,...,$A_N$ ($0 \leq A_i \leq 10^9$)


-----Output-----

The first and only line of output consists of one string, the name of the winner. If Alice won, print "Alice", otherwise, print "Bob".


-----Examples-----

Input
1
5
Output
Alice
Input
3
5 4 5
Output
Alice
Input
6
5 8 2 1 10 9
Output
Bob


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S of length N consisting of lowercase English letters.
Process Q queries of the following two types:
 - Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)
 - Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

-----Constraints-----
 - N, Q, i_q, l_q, and r_q are integers.
 - S is a string consisting of lowercase English letters.
 - c_q is a lowercase English letter.
 - 1 \leq N \leq 500000
 - 1 \leq Q \leq 20000
 - |S| = N
 - 1 \leq i_q \leq N
 - 1 \leq l_q \leq r_q \leq N
 - There is at least one query of type 2 in each testcase.

-----Input-----
Input is given from Standard Input in the following format:
N
S
Q
Query_1
\vdots
Query_Q

Here, Query_i in the 4-th through (Q+3)-th lines is one of the following:
1 i_q c_q

2 l_q r_q

-----Output-----
For each query of type 2, print a line containing the answer.

-----Sample Input-----
7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

-----Sample Output-----
3
1
5

In the first query, cdbb contains three kinds of letters: b , c , and d, so we print 3.
In the second query, S is modified to abcdzbd.
In the third query, a contains one kind of letter: a, so we print 1.
In the fourth query, S is modified to abcazbd.
In the fifth query, S does not change and is still abcazbd.
In the sixth query, abcazbd contains five kinds of letters: a, b, c, d, and z, so we print 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The premier of the anticipated action film No Thyme to Fry is right around the corner, and it is time to give early screenings to film critics so that they can review it. A small cinema has been selected to show these early screenings. 

There are $n$ critics numbered from $1$ to $n$ scheduled to watch the movie early, and each of them will watch it separately. After watching it, they will immediately give it a score from $0$ to $m$. Susan, the cinema owner, has carefully looked at every critic’s social media and already knows that the $i$th critic thinks the movie is worth a score of $a_ i$. However, the $i$th critic will not simply give the movie a score of $a_ i$ like you would expect, because they also take into account the scores that the other critics gave. Here is how they behave:
 - The first critic to arrive will be so happy that they are the first to review the movie that they will give it a score of $m$ regardless of their initial opinion.
 - Every subsequent critic will look at the average score given by the previous critics. If this number is smaller than or equal to the initial opinion $a_ i$ then the critic will give it a score of $m$, otherwise they will give it a $0$.

Susan thinks the critics’ behaviour is ridiculous. She has watched the movie, and it is clearly worth a score of exactly $k/n$ and nothing else! But Susan is the owner of the cinema, so she gets to decide in what order to invite the critics. Your task is to find a permutation of $1,2, \dots , n$ so that if the critics arrive in this order the average score will be exactly $k/n$.Input

The first line of input contains three integers $n$, $m$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq m \leq 10^4$, $0 \leq k \leq n \cdot m$). The second line contains the $n$ integers $a_1, a_2, \ldots , a_ n$ ($0 \le a_ i \le m$ for each $i$), the $n$ critic scores as described above.Output

If the critics can be ordered in such a way that the resulting average score is exactly $k/n$, then output $n$ integers $p_1, \ldots , p_ n$ ($1 \le p_ i \le n$), where $p_ i$ indicates that the $i$th critic to visit the cinema is the critic numbered $p_ i$. This list of integers should be a permutation such that the average score given by the critics is $k/n$. If there are multiple solutions any one will be accepted.

Otherwise, if there is no such way to order the critics, output “impossible”.

-----Examples-----
Sample Input:
5 10 30
10 5 3 1 3
Sample Output:
3 5 2 1 4

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