vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ibis is fighting with a monster.
The health of the monster is H.
Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.
The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.
Ibis wins when the health of the monster becomes 0 or below.
Find the minimum total Magic Points that have to be consumed before winning.

-----Constraints-----
 - 1 \leq H \leq 10^4
 - 1 \leq N \leq 10^3
 - 1 \leq A_i \leq 10^4
 - 1 \leq B_i \leq 10^4
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
H N
A_1 B_1
:
A_N B_N

-----Output-----
Print the minimum total Magic Points that have to be consumed before winning.

-----Sample Input-----
9 3
8 3
4 2
2 1

-----Sample Output-----
4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.
Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.
In this way, we can win at the total cost of 4 Magic Points.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the sequence `a(1) = 7, a(n) = a(n-1) + gcd(n, a(n-1)) for n >= 2`: 

`7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69, 72, 73...`.

Let us take the differences between successive elements of the sequence and
get a second sequence `g: 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1...`.

For the sake of uniformity of the lengths of sequences **we add** a `1` at the head of g:

`g: 1, 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1...`

Removing the 1s gives a third sequence:
`p: 5, 3, 11, 3, 23, 3...`
where you can see prime numbers.

#Task:
Write functions:
```
1: an(n) with parameter n: returns the first n terms of the series a(n) (not tested)

2: gn(n) with parameter n: returns the first n terms of the series g(n) (not tested)

3: countOnes(n) with parameter n: returns the number of 1 in g(n) 
    (don't forget to add a `1` at the head) # (tested)
    
4: p(n) with parameter n: returns an array of n unique prime numbers (not tested)

5: maxp(n) with parameter n: returns the biggest prime number of the sequence pn(n) # (tested)

6: anOver(n) with parameter n: returns an array (n terms) of the a(i)/i for every i such g(i) != 1 (not tested but interesting result)

7: anOverAverage(n) with parameter n: returns as an *integer* the average of anOver(n)  (tested)
```

#Note:
You can write directly functions `3:`, `5:` and `7:`. There is no need to write functions `1:`, `2:`, `4:` `6:`
except out of pure curiosity.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence $A_1, A_2, \ldots, A_N$. You have to split the array into maximum number of non-empty subarrays such that the gcd of elements of each subarray is equal to 1.

-----Input:-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output:-----
For each test case, print a single line containing one integer ― the maximum number of subarrays formed, or $-1$ if the array cannot be split while satisfying the above condition.

-----Constraints-----
- $1 \le T \le 3$
- $1 \le N \le 5 \cdot 10^5$
- $1 \le A_i \le 10^6$ for each valid $i$

-----Sample Input:-----
2
3
2 2 3
4
2 3 3 2

-----Sample Output:-----
1
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have moved to Colorland. Currency System here consists of various type of coins.

Each coin in Colorland has exactly one color. The coin color follow these rules. 
All coins of same denomination have same color.
No two coins of different type have same color.

You know all coin denominations used in Colorland, but you dont know their colors. You dont even know the set of colors used for them.

For each denomination you would like to know the color of coins of that denomination.
For that, you have a credit card and an ATM , both having infinite amount.

You can ask for some amount X from the ATM. The ATM will provide you with the required amount of money with those coins.
It uses the following pseudocode to uniquely determine the set of coins it will use to pay you X amount of money.
    func(x, a, n) // a is array containing different denominations
        sort(a, n)
        for i = n to 1
            t = x / a[i]
            give t coins of i'th type
            x -= t * a[i]
You will be given long A[] which shows the different coin denominations available. A[1] will always be 1 so ATM can always give desired amount of money.

Determine if there exists some X, for which the number of coins of each denomination given by ATM is different and non-zero so that you can identify what color
each denomination coins are of.

If there exists some X, print "YES" else print "NO".

Input Format:

First line contains T, the number of test cases.
For each test case, first line contains N, the number of different coin denominations.
Second line contains N distinct integers which are sorted in ascending order.

Output Format :

Print YES/NO for each test case in a single line.

Constrains :

1 ≤ T ≤ 10^6
1 ≤ N ≤ 10^6
1 ≤ sum of N over all cases ≤ 10^6
1 ≤ A[i] ≤ 10^18

SAMPLE INPUT
2
3
1 3 6
3
1 2 4

SAMPLE OUTPUT
YES
NO

Explanation

For test case 1, take X = 23.
ATM will give 3 coins of 6$, 1 coin of 3$ and 2 coins of 1$
In {3 , 1 , 2}, each number is non-zero and distinct. Hence, you can identify color of each denomination. 

For test case 2, there doesn't exist any valid X.
For e.g. taking X = 7,
ATM will give 1 coin of 4$, 1 coin of 2$ and 1 coin of 1$
In  {1 , 1 , 1} , all elements are not distinct. Hence it is not valid.

Similarly, For X = 10, 
ATM will give 2 coins of 4$, 1 coin of 2$ and 0 coins of 1$
In {2 , 1 , 0}, all elements are not non-zero. Hence it is not valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a list of $N$ numbers $a_1,a_2,\ldots,a_n$. For each element at position $\boldsymbol{i}$ ($1\leq i\leq N$), we define $\text{Left}(i)$ and $\textit{Right}(i)$ as: 

$\text{Left}(i)$ = closest index j such that j < i and $a_j>a_i$. If no such j exists then $\text{Left}(i)$ = 0. 

$\textit{Right}(i)$ = closest index k such that k > i and $a_k>a_i$. If no such k exists then $\textit{Right}(i)$ = 0.   

We define $\textit{IndexProduct(i)}$ = $\text{Left}(i)$ * $\textit{Right}(i)$. You need to find out the maximum $\textit{IndexProduct(i)}$ among all i.

Input Format

The first line contains an integer $N$, the number of integers.
The next line contains the $N$ integers describing the list a[1..N].

Constraints 

$1\leq N\leq10^5$ 

$1\leq a_i\leq10^9$

Output Format

Output the maximum $\textit{IndexProduct}$ among all indices from $1$ to $N$. 

Sample Input
5
5 4 3 4 5

Sample Output
8

Explanation

We can compute the following:

$IndexProduct(1)=0$ 

$IndexProduct(2)=1\times5=5$ 

$IndexProduct(3)=2\times4=8$ 

$IndexProduct(4)=1\times5=5$ 

$IndexProduct(5)=0$

The largest of these is 8, so it is the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A balancing network is an abstract device built up of N wires, thought of as running from left to right, and M balancers that connect pairs of wires. The wires are numbered from 1 to N from top to bottom, and the balancers are numbered from 1 to M from left to right. Balancer i connects wires x_i and y_i (x_i < y_i).

pic1-small-2acea94b.png

Each balancer must be in one of two states: up or down.

Consider a token that starts moving to the right along some wire at a point to the left of all balancers. During the process, the token passes through each balancer exactly once. Whenever the token encounters balancer i, the following happens:

* If the token is moving along wire x_i and balancer i is in the down state, the token moves down to wire y_i and continues moving to the right.
* If the token is moving along wire y_i and balancer i is in the up state, the token moves up to wire x_i and continues moving to the right.
* Otherwise, the token doesn't change the wire it's moving along.



Let a state of the balancing network be a string of length M, describing the states of all balancers. The i-th character is `^` if balancer i is in the up state, and `v` if balancer i is in the down state.

A state of the balancing network is called uniforming if a wire w exists such that, regardless of the starting wire, the token will always end up at wire w and run to infinity along it. Any other state is called non-uniforming.

You are given an integer T (1 \le T \le 2). Answer the following question:

* If T = 1, find any uniforming state of the network or determine that it doesn't exist.
* If T = 2, find any non-uniforming state of the network or determine that it doesn't exist.



Note that if you answer just one kind of questions correctly, you can get partial score.

Constraints

* 2 \leq N \leq 50000
* 1 \leq M \leq 100000
* 1 \leq T \leq 2
* 1 \leq x_i < y_i \leq N
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N M T
x_1 y_1
x_2 y_2
:
x_M y_M


Output

Print any uniforming state of the given network if T = 1, or any non-uniforming state if T = 2. If the required state doesn't exist, output `-1`.

Examples

Input

4 5 1
1 3
2 4
1 2
3 4
2 3


Output

^^^^^


Input

4 5 2
1 3
2 4
1 2
3 4
2 3


Output

v^^^^


Input

3 1 1
1 2


Output

-1


Input

2 1 2
1 2


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp took $n$ videos, the duration of the $i$-th video is $a_i$ seconds. The videos are listed in the chronological order, i.e. the $1$-st video is the earliest, the $2$-nd video is the next, ..., the $n$-th video is the last.

Now Polycarp wants to publish exactly $k$ ($1 \le k \le n$) posts in Instabram. Each video should be a part of a single post. The posts should preserve the chronological order, it means that the first post should contain one or more of the earliest videos, the second post should contain a block (one or more videos) going next and so on. In other words, if the number of videos in the $j$-th post is $s_j$ then:

  $s_1+s_2+\dots+s_k=n$ ($s_i>0$),  the first post contains the videos: $1, 2, \dots, s_1$;  the second post contains the videos: $s_1+1, s_1+2, \dots, s_1+s_2$;  the third post contains the videos: $s_1+s_2+1, s_1+s_2+2, \dots, s_1+s_2+s_3$;  ...  the $k$-th post contains videos: $n-s_k+1,n-s_k+2,\dots,n$. 

Polycarp is a perfectionist, he wants the total duration of videos in each post to be the same.

Help Polycarp to find such positive integer values $s_1, s_2, \dots, s_k$ that satisfy all the conditions above.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$). The next line contains $n$ positive integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$), where $a_i$ is the duration of the $i$-th video.


-----Output-----

If solution exists, print "Yes" in the first line. Print $k$ positive integers $s_1, s_2, \dots, s_k$ ($s_1+s_2+\dots+s_k=n$) in the second line. The total duration of videos in each post should be the same. It can be easily proven that the answer is unique (if it exists).

If there is no solution, print a single line "No".


-----Examples-----
Input
6 3
3 3 1 4 1 6

Output
Yes
2 3 1 
Input
3 3
1 1 1

Output
Yes
1 1 1 
Input
3 3
1 1 2

Output
No
Input
3 1
1 10 100

Output
Yes
3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are playing a video game and you have just reached the bonus level, where the only possible goal is to score as many points as possible. Being a perfectionist, you've decided that you won't leave this level until you've gained the maximum possible number of points there.

The bonus level consists of *n* small platforms placed in a line and numbered from 1 to *n* from left to right and (*n*<=-<=1) bridges connecting adjacent platforms. The bridges between the platforms are very fragile, and for each bridge the number of times one can pass this bridge from one of its ends to the other before it collapses forever is known in advance.

The player's actions are as follows. First, he selects one of the platforms to be the starting position for his hero. After that the player can freely move the hero across the platforms moving by the undestroyed bridges. As soon as the hero finds himself on a platform with no undestroyed bridge attached to it, the level is automatically ended. The number of points scored by the player at the end of the level is calculated as the number of transitions made by the hero between the platforms. Note that if the hero started moving by a certain bridge, he has to continue moving in the same direction until he is on a platform.

Find how many points you need to score to be sure that nobody will beat your record, and move to the next level with a quiet heart.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=105) — the number of platforms on the bonus level. The second line contains (*n*<=-<=1) integers *a**i* (1<=≤<=*a**i*<=≤<=109, 1<=≤<=*i*<=&lt;<=*n*) — the number of transitions from one end to the other that the bridge between platforms *i* and *i*<=+<=1 can bear.

Output Specification:
Print a single integer — the maximum number of points a player can get on the bonus level.

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

Demo Input:
['5\n2 1 2 1\n']

Demo Output:
['5\n']

Note:
One possibility of getting 5 points in the sample is starting from platform 3 and consequently moving to platforms 4, 3, 2, 1 and 2. After that the only undestroyed bridge is the bridge between platforms 4 and 5, but this bridge is too far from platform 2 where the hero is located now.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jem is famous for his laziness at school. He always leaves things to last minute. Now Jem has N problems in the assignment of "Advanced topics in algorithm" class to solved. The assignment is due tomorrow and as you may guess he hasn't touch any of the problems. Fortunately he got a plan as always.

The first step will be buying a pack of Red Bull and then to work as hard as he can. Here is how he is going to spend the remaining time:

Jem will not take a break until he finishes at least half of the remaining problems. Formally, if N is even then he will take he first break after finishing N / 2 problems. If N is odd then the break will be after he done (N + 1) / 2 problems. Each of his break will last for B minutes. Initially, he takes M minutes in solving a problem, after each break he will take twice more time in solving a problem, i.e. 2 * M minutes per problem after the first break.

Jem will start working soon and ask you to help him calculate how much time it will take until he finish the last problem!

-----Input-----

The first line contains a single integer T represents the number of test cases in the input.
Each line in the next T line contains three integers N, B and M represents a test case.

-----Output-----

For each test case output a single line containing an integer represent how much time Jem will need (in minutes).

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N, B, M ≤ 108

-----Example-----
Input:
2
9 1 2
123456 123456 123456

Output:
45
131351258112

-----Explanation-----

In the first test case, Jem will proceed as below:

- Initially, Jem has 9 problems to solve. since it is an odd number, Jem will finish the first (9 + 1) / 2 = 5 problems with speed of 2 minutes/problem.
- After that, Jem takes 1 minute break.
- Now he has 4 problems to solve, which is an even number, so Jem will solve the next 4 / 2 = 2 problems. his speed after the first break has now became 4 minutes/problem.

- Again, he takes a 1 minute break.
- he has now 2 problems left so he do one more problem in 8 minutes.
- He takes 1 minute break.
- he solves the last problem in 16 minutes.

So, Jem will need time = 5 × 2 + 1 + 2 × 4 + 1 + 8 + 1 + 16  = 45

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?



An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:


Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As you didn’t show up to the yearly general meeting of the Nordic Club of Pin Collectors, you were unanimously elected to organize this years excursion to Pin City. You are free to choose from a number of weekends this autumn, and have to find a suitable hotel to stay at, preferably as cheap as possible. 

You have some constraints: The total cost of the trip must be within budget, of course. All participants must stay at the same hotel, to avoid last years catastrophe, where some members got lost in the city, never being seen again.

-----Input-----
The first line of input consists of four integers: $1 \leq N \leq 200$, the number of participants, $1 \leq B \leq 500000$, the budget, $1 \leq H \leq 18$, the number of hotels to consider, and $1 \leq W \leq 13$, the number of weeks you can choose between. Then follow two lines for each of the $H$ hotels. The first gives $1 \leq p \leq 10000$, the price for one person staying the weekend at the hotel. The second contains $W$ integers, $0 \leq a \leq 1000$, giving the number of available beds for each weekend at the hotel.

-----Output-----
Output the minimum cost of the stay for your group, or “stay home” if nothing can be found within the budget.

-----Examples-----
Sample Input:
3 1000 2 3
200
0 2 2
300
27 3 20
Sample Output:
900

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A format for expressing an ordered list of integers is to use a comma separated list of either

* individual integers
* or a range of integers denoted by the starting integer separated from the end integer in the range by a dash, '-'. The range includes all integers in the interval including both endpoints.  It is not considered a range unless it spans at least 3 numbers. For example "12,13,15-17"

Complete the solution  so that it takes a list of integers in increasing order and returns a correctly formatted string in the range format. 

**Example:**

```python
solution([-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20])
# returns "-6,-3-1,3-5,7-11,14,15,17-20"
```

```C#
RangeExtraction.Extract(new[] {-6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20});
# returns "-6,-3-1,3-5,7-11,14,15,17-20"
```

*Courtesy of rosettacode.org*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Walrusland public transport tickets are characterized by two integers: by the number of the series and by the number of the ticket in the series. Let the series number be represented by a and the ticket number — by b, then a ticket is described by the ordered pair of numbers (a, b). 

The walruses believe that a ticket is lucky if a * b = rev(a) * rev(b). The function rev(x) reverses a number written in the decimal system, at that the leading zeroes disappear. For example, rev(12343) = 34321, rev(1200) = 21.

The Public Transport Management Committee wants to release x series, each containing y tickets, so that at least w lucky tickets were released and the total number of released tickets (x * y) were minimum. The series are numbered from 1 to x inclusive. The tickets in each series are numbered from 1 to y inclusive. The Transport Committee cannot release more than maxx series and more than maxy tickets in one series.

Input

The first line contains three integers maxx, maxy, w (1 ≤ maxx, maxy ≤ 105, 1 ≤ w ≤ 107).

Output

Print on a single line two space-separated numbers, the x and the y. If there are several possible variants, print any of them. If such x and y do not exist, print a single number  - 1.

Examples

Input

2 2 1


Output

1 1

Input

132 10 35


Output

7 5

Input

5 18 1000


Output

-1


Input

48 132 235


Output

22 111

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef Al Gorithm was reading a book about climate and oceans when he encountered the word “glaciological”. He thought it was quite curious, because it has the following interesting property: For every two letters in the word, if the first appears x times and the second appears y times, then |x - y| ≤ 1.
Chef Al was happy about this and called such words 1-good words. He also generalized the concept: He said a word was K-good if for every two letters in the word, if the first appears x times and the second appears y times, then |x - y| ≤ K.
Now, the Chef likes K-good words a lot and so was wondering: Given some word w, how many letters does he have to remove to make it K-good?

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case consists of a single line containing two things: a word w and an integer K, separated by a space.

-----Output-----
For each test case, output a single line containing a single integer: the minimum number of letters he has to remove to make the word K-good.

-----Constraints-----
- 1 ≤ T ≤ 30
- 1 ≤ |w| ≤ 105
- 0 ≤ K ≤ 105
- w contains only lowercase English letters.

-----Example-----
Input:
4
glaciological 1
teammate 0
possessions 3
defenselessness 3

Output:
0
0
1
2

-----Explanation-----
Example case 1. The word “glaciological” is already 1-good, so the Chef doesn't have to remove any letter.
Example case 2. Similarly, “teammate” is already 0-good.
Example case 3. The word “possessions” is 4-good. To make it 3-good, the Chef can remove the last s to make “possession”.
Example case 4. The word “defenselessness” is 4-good. To make it 3-good, Chef Al can remove an s and an e to make, for example, “defenslesness”. Note that the word doesn't have to be a valid English word.

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