apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya plays the LionAge II. He was bored of playing with a stupid computer, so he installed this popular MMORPG, to fight with his friends. Vasya came up with the name of his character — non-empty string s, consisting of a lowercase Latin letters. However, in order not to put up a front of friends, Vasya has decided to change no more than k letters of the character name so that the new name sounded as good as possible. Euphony of the line is defined as follows: for each pair of adjacent letters x and y (x immediately precedes y) the bonus c(x, y) is added to the result. Your task is to determine what the greatest Euphony can be obtained by changing at most k letters in the name of the Vasya's character.

## Input Format
The first line contains character's name s and an integer number k (0 ≤ k ≤ 100). The length of the nonempty string s does not exceed 100. The second line contains an integer number n (0 ≤ n ≤ 676) — amount of pairs of letters, giving bonus to the euphony. The next n lines contain description of these pairs «x y c», which means that sequence xy gives bonus c (x, y — lowercase Latin letters,  - 1000 ≤ c ≤ 1000). It is guaranteed that no pair x y mentioned twice in the input data.

## Output Format
Output the only number — maximum possible euphony оf the new character's name.

## Examples
```input
winner 4
4
s e 7
o s 8
l o 13
o o 8
```
```output
36
```
-----
```input
abcdef 1
5
a b -10
b c 5
c d 5
d e 5
e f 5
```
```output
20
```

## Note
In the first example the most euphony name will be looser. It is easy to calculate that its euphony is 36.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya plays FreeDiv. In this game he manages a huge state, which has n cities and m two-way roads between them. Unfortunately, not from every city you can reach any other one moving along these roads. Therefore Vasya decided to divide the state into provinces so that in every province, one could reach from every city all the cities of the province, but there are no roads between provinces.

Unlike other turn-based strategies, in FreeDiv a player has the opportunity to build tunnels between cities. The tunnels are two-way roads along which one can move armies undetected by the enemy. However, no more than one tunnel can be connected to each city. As for Vasya, he wants to build a network of tunnels so that any pair of cities in his state were reachable by some path consisting of roads and a tunnels. But at that no more than k tunnels are connected to each province (otherwise, the province will be difficult to keep in case other provinces are captured by enemy armies).

Vasya discovered that maybe he will not be able to build such a network for the current condition of the state. Maybe he'll have first to build several roads between cities in different provinces to merge the provinces. Your task is to determine the minimum number of roads Vasya needs to build so that it was possible to build the required network of tunnels in the resulting state.

## Input Format
The first line contains three integers n, m and k (1 ≤ n, k ≤ 106, 0 ≤ m ≤ 106). Each of the next m lines contains two integers. They are the numbers of cities connected by a corresponding road. No road connects city to itself and there is at most one road between each pair of cities.

## Output Format
Print a single number, the minimum number of additional roads.

## Examples
```input
3 3 2
1 2
2 3
3 1
```
```output
0
```
-----
```input
4 2 2
1 2
3 4
```
```output
0
```
-----
```input
4 0 2
```
```output
1
```

## Note
In the first example only one province exists, so it is not necessary to build any tunnels or roads.

In the second example two provinces exist. It is possible to merge the provinces by building a tunnel between cities 1 and 3.

In the third example at least one additional road is necessary. For example it is possible to build additional road between cities 1 and 2 and build two tunnels between cities 1 and 3, 2 and 4 after that.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya plays The Elder Trolls III: Morrowindows. He has a huge list of items in the inventory, however, there is no limits on the size of things. Vasya does not know the total amount of items but he is sure that are not more than x and not less than 2 items in his inventory. A new patch for the game appeared to view inventory in n different modes. Displaying in mode i is a partition of all inventory items on pages, each of which (except for maybe the last one) shows exactly ai items. In addition, each mode shows how many pages bi is in a complete list. Great! Perhaps this information will be enough for Vasya to find the required number. Moreover, it is very interesting, what is the fewest number of modes in which Vasya can see inventory to determine the number of items in it?

Vasya cannot use the information that was received while looking on inventory in some mode for selection of next actions. I. e. Vasya chooses some set of modes first, and then sees all the results and determines the size.

Knowing the number of ai, x and assuming that Vasya is very smart, check whether he can uniquely determine the number of items in his inventory, and how many modes he will need to do that if he knows numbers ai, x and he is able to know number bi after viewing items in mode i.

## Input Format
The first line contains two integers n and x (0 ≤ n ≤ 105, 2 ≤ x ≤ 109). The second line contains integers ai (1 ≤ ai ≤ 109). Some numbers among all ai may be equal.

## Output Format
Output the fewest amount of modes required to uniquely determine amount of items in the inventory. If there is no solution output  - 1.

## Examples
```input
2 4
2 3
```
```output
2
```
-----
```input
1 4
2
```
```output
-1
```

## Note
In the second example Vasya is not able to determine items count uniquely because 3 items, as well as 4 items, can be displayed on two pages.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Ostap is preparing to play chess again and this time he is about to prepare. Thus, he was closely monitoring one recent chess tournament. There were m players participating and each pair of players played exactly one game. The victory gives 2 points, draw — 1 points, lose — 0 points.

Ostap is lazy, so he never tries to remember the outcome of each game. Instead, he computes the total number of points earned by each of the players (the sum of his points in all games which he took part in), sort these value in non-ascending order and then remembers first n integers in this list.

Now the Great Strategist Ostap wonders whether he remembers everything correct. He considers that he is correct if there exists at least one tournament results table such that it will produce the given integers. That means, if we count the sum of points for each player, sort them and take first n elements, the result will coincide with what Ostap remembers. Can you check if such table exists?

## Input Format
The first line of the input contains two integers m and n (1 ≤ n ≤ m ≤ 3000) — the number of participants of the tournament and the number of top results Ostap remembers.

The second line contains n integers, provided in non-ascending order — the number of points earned by top participants as Ostap remembers them. It's guaranteed that this integers are non-negative and do not exceed 2·m.

## Output Format
If there is no tournament such that Ostap can obtain the given set of integers using the procedure described in the statement, then print "no" in the only line of the output. Otherwise, the first line of the output should contain the word "yes". Next m lines should provide the description of any valid tournament. Each of these lines must contain m characters 'X', 'W', 'D' and 'L'. Character 'X' should always be located on the main diagonal (and only there), that is on the i-th position of the i-th string. Character 'W' on the j-th position of the i-th string means that the i-th player won the game against the j-th. In the same way character 'L' means loose and 'D' means draw.

The table you print must be consistent and the points earned by best n participants should match the memory of Ostap. If there are many possible answers, print any of them.

## Examples
```input
5 5
8 6 4 2 0
```
```output
yes
XWWWW
LXWWW
LLXWW
LLLXW
LLLLX
```
-----
```input
5 1
9
```
```output
no
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Limak is going to participate in a contest on the last day of the 2016. The contest will start at 20:00 and will last four hours, exactly until midnight. There will be n problems, sorted by difficulty, i.e. problem 1 is the easiest and problem n is the hardest. Limak knows it will take him 5·i minutes to solve the i-th problem.

Limak's friends organize a New Year's Eve party and Limak wants to be there at midnight or earlier. He needs k minutes to get there from his house, where he will participate in the contest first.

How many problems can Limak solve if he wants to make it to the party?

## Input Format
The only line of the input contains two integers n and k (1 ≤ n ≤ 10, 1 ≤ k ≤ 240) — the number of the problems in the contest and the number of minutes Limak needs to get to the party from his house.

## Output Format
Print one integer, denoting the maximum possible number of problems Limak can solve so that he could get to the party at midnight or earlier.

## Examples
```input
3 222
```
```output
2
```
-----
```input
4 190
```
```output
4
```
-----
```input
7 1
```
```output
7
```

## Note
In the first sample, there are 3 problems and Limak needs 222 minutes to get to the party. The three problems require 5, 10 and 15 minutes respectively. Limak can spend 5 + 10 = 15 minutes to solve first two problems. Then, at 20:15 he can leave his house to get to the party at 23:57 (after 222 minutes). In this scenario Limak would solve 2 problems. He doesn't have enough time to solve 3 problems so the answer is 2.

In the second sample, Limak can solve all 4 problems in 5 + 10 + 15 + 20 = 50 minutes. At 20:50 he will leave the house and go to the party. He will get there exactly at midnight.

In the third sample, Limak needs only 1 minute to get to the party. He has enough time to solve all 7 problems.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
In this problem we assume the Earth to be a completely round ball and its surface a perfect sphere. The length of the equator and any meridian is considered to be exactly 40 000 kilometers. Thus, travelling from North Pole to South Pole or vice versa takes exactly 20 000 kilometers.

Limak, a polar bear, lives on the North Pole. Close to the New Year, he helps somebody with delivering packages all around the world. Instead of coordinates of places to visit, Limak got a description how he should move, assuming that he starts from the North Pole. The description consists of n parts. In the i-th part of his journey, Limak should move ti kilometers in the direction represented by a string diri that is one of: "North", "South", "West", "East".

Limak isn’t sure whether the description is valid. You must help him to check the following conditions:

- If at any moment of time (before any of the instructions or while performing one of them) Limak is on the North Pole, he can move only to the South.
- If at any moment of time (before any of the instructions or while performing one of them) Limak is on the South Pole, he can move only to the North.
- The journey must end on the North Pole.

Check if the above conditions are satisfied and print "YES" or "NO" on a single line.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 50).

The i-th of next n lines contains an integer ti and a string diri (1 ≤ ti ≤ 106, $${ dir } _ { i } \in \{ \mathrm { N o r t h, ~ S o u t h, ~ W e s t, ~ E a s t } \}$$) — the length and the direction of the i-th part of the journey, according to the description Limak got.

## Output Format
Print "YES" if the description satisfies the three conditions, otherwise print "NO", both without the quotes.

## Examples
```input
5
7500 South
10000 East
3500 North
4444 West
4000 North
```
```output
YES
```
-----
```input
2
15000 South
4000 East
```
```output
NO
```
-----
```input
5
20000 South
1000 North
1000000 West
9000 North
10000 North
```
```output
YES
```
-----
```input
3
20000 South
10 East
20000 North
```
```output
NO
```
-----
```input
2
1000 North
1000 South
```
```output
NO
```
-----
```input
4
50 South
50 North
15000 South
15000 North
```
```output
YES
```

## Note
Drawings below show how Limak's journey would look like in first two samples. In the second sample the answer is "NO" because he doesn't end on the North Pole.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
The New Year tree is an infinite perfect binary tree rooted in the node 1. Each node v has two children: nodes indexed (2·v) and (2·v + 1).

Polar bears love decorating the New Year tree and Limak is no exception. As he is only a little bear, he was told to decorate only one simple path between some pair of nodes. Though he was given an opportunity to pick the pair himself! Now he wants to know the number of unordered pairs of indices (u, v) (u ≤ v), such that the sum of indices of all nodes along the simple path between u and v (including endpoints) is equal to s. Can you help him and count this value?

## Input Format
The only line of the input contains a single integer s (1 ≤ s ≤ 1015).

## Output Format
Print one integer, denoting the number of unordered pairs of nodes indices defining simple paths with the sum of indices of vertices equal to s.

## Examples
```input
10
```
```output
4
```

## Note
In sample test, there are 4 paths with the sum of indices equal to 10:

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Ilya is an experienced player in tic-tac-toe on the 4 × 4 field. He always starts and plays with Xs. He played a lot of games today with his friend Arseny. The friends became tired and didn't finish the last game. It was Ilya's turn in the game when they left it. Determine whether Ilya could have won the game by making single turn or not.

The rules of tic-tac-toe on the 4 × 4 field are as follows. Before the first turn all the field cells are empty. The two players take turns placing their signs into empty cells (the first player places Xs, the second player places Os). The player who places Xs goes first, the another one goes second. The winner is the player who first gets three of his signs in a row next to each other (horizontal, vertical or diagonal).

## Input Format
The tic-tac-toe position is given in four lines.

Each of these lines contains four characters. Each character is '.' (empty cell), 'x' (lowercase English letter x), or 'o' (lowercase English letter o). It is guaranteed that the position is reachable playing tic-tac-toe, and it is Ilya's turn now (in particular, it means that the game is not finished). It is possible that all the cells are empty, it means that the friends left without making single turn.

## Output Format
Print single line: "YES" in case Ilya could have won by making single turn, and "NO" otherwise.

## Examples
```input
xx..
.oo.
x...
oox.
```
```output
YES
```
-----
```input
x.ox
ox..
x.o.
oo.x
```
```output
NO
```
-----
```input
x..x
..oo
o...
x.xo
```
```output
YES
```
-----
```input
o.x.
o...
.x..
ooxx
```
```output
NO
```

## Note
In the first example Ilya had two winning moves: to the empty cell in the left column and to the leftmost empty cell in the first row.

In the second example it wasn't possible to win by making single turn.

In the third example Ilya could have won by placing X in the last row between two existing Xs.

In the fourth example it wasn't possible to win by making single turn.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket.

The goods in the supermarket have unique integer ids. Also, for every integer there is a product with id equal to this integer. Fedor has n discount coupons, the i-th of them can be used with products with ids ranging from li to ri, inclusive. Today Fedor wants to take exactly k coupons with him.

Fedor wants to choose the k coupons in such a way that the number of such products x that all coupons can be used with this product x is as large as possible (for better understanding, see examples). Fedor wants to save his time as well, so he asks you to choose coupons for him. Help Fedor!

## Input Format
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 3·105) — the number of coupons Fedor has, and the number of coupons he wants to choose.

Each of the next n lines contains two integers li and ri ( - 109 ≤ li ≤ ri ≤ 109) — the description of the i-th coupon. The coupons can be equal.

## Output Format
In the first line print single integer — the maximum number of products with which all the chosen coupons can be used. The products with which at least one coupon cannot be used shouldn't be counted.

In the second line print k distinct integers p1, p2, ..., pk (1 ≤ pi ≤ n) — the ids of the coupons which Fedor should choose.

If there are multiple answers, print any of them.

## Examples
```input
4 2
1 100
40 70
120 130
125 180
```
```output
31
1 2
```
-----
```input
3 2
1 12
15 20
25 30
```
```output
0
1 2
```
-----
```input
5 2
1 10
5 15
14 50
30 70
99 100
```
```output
21
3 4
```

## Note
In the first example if we take the first two coupons then all the products with ids in range [40, 70] can be bought with both coupons. There are 31 products in total.

In the second example, no product can be bought with two coupons, that is why the answer is 0. Fedor can choose any two coupons in this example.

Now solve the problem and return the code.