真的不是我托更，只是因为我一题都没写出来orz

# A. Masha and Bears

2 seconds

256 megabytes

standard input

standard output

A family consisting of father bear, mother bear and son bear owns three cars. Father bear can climb into the largest car and he likes it. Also, mother bear can climb into the middle car and she likes it. Moreover, son bear can climb into the smallest car and he likes it. It’s known that the largest car is strictly larger than the middle car, and the middle car is strictly larger than the smallest car.

Masha came to test these cars. She could climb into all cars, but she liked only the smallest car.

It’s known that a character with size *a* can climb into some car with size *b* if and only if *a* ≤ *b*, he or she likes it if and only if he can climb into this car and 2*a* ≥ *b*.

You are given sizes of bears and Masha. Find out some possible integer non-negative sizes of cars.

### Input

You are given four integers *V*_{1}, *V*_{2}, *V*_{3}, *V*_{m}(1 ≤ *V*_{i} ≤ 100) — sizes of father bear, mother bear, son bear and Masha, respectively. It’s guaranteed that *V*_{1} > *V*_{2} > *V*_{3}.

### Output

Output three integers — sizes of father bear’s car, mother bear’s car and son bear’s car, respectively.

If there are multiple possible solutions, print any.

If there is no solution, print “-1” (without quotes).

### Examples

##### input

1 |
50 30 10 10 |

##### output

1 2 3 |
50 30 10 |

##### input

1 |
100 50 10 21 |

##### output

1 |
-1 |

### Note

In first test case all conditions for cars’ sizes are satisfied.

In second test case there is no answer, because Masha should be able to climb into smallest car (so size of smallest car in not less than 21), but son bear should like it, so maximum possible size of it is 20.

# B. Tic-Tac-Toe

2 seconds

256 megabytes

standard input

standard output

Two bears are playing tic-tac-toe via mail. It’s boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules.

The game is played on the following field.

*x*

_{l},

*y*

_{l}) in some small field, the next move should be done in one of the cells of the small field with coordinates (

*x*

_{l},

*y*

_{l}). For example, if in the first move a player puts his chip to lower left cell of central field, then the second player on his next move should put his chip into some cell of lower left field (pay attention to the first test case). If there are no free cells in the required field, the player can put his chip to any empty cell on any field.

You are given current state of the game and coordinates of cell in which the last move was done. You should find all cells in which the current player can put his chip.

A hare works as a postman in the forest, he likes to foul bears. Sometimes he changes the game field a bit, so the current state of the game could be unreachable. However, after his changes the cell where the last move was done is not empty. You don’t need to find if the state is unreachable or not, just output possible next moves according to the rules.

### Input

First 11 lines contains descriptions of table with 9 rows and 9 columns which are divided into 9 small fields by spaces and empty lines. Each small field is described by 9 characters without spaces and empty lines. character “x” (ASCII-code 120) means that the cell is occupied with chip of the first player, character “o” (ASCII-code 111) denotes a field occupied with chip of the second player, character “.” (ASCII-code 46) describes empty cell.

The line after the table contains two integers *x* and *y* (1 ≤ *x*, *y* ≤ 9). They describe coordinates of the cell in table where the last move was done. Rows in the table are numbered from up to down and columns are numbered from left to right.

It’s guaranteed that cell where the last move was done is filled with “x” or “o“. Also, it’s guaranteed that there is at least one empty cell. It’s not guaranteed that current state of game is reachable.

### Output

Output the field in same format with characters “!” (ASCII-code 33) on positions where the current player can put his chip. All other cells should not be modified.

### Examples

##### input

1 2 3 4 5 6 7 8 9 10 11 12 |
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... x.. ... ... ... ... ... ... ... ... ... ... 6 4 |

##### output

1 2 3 4 5 6 7 8 9 10 11 |
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... x.. ... !!! ... ... !!! ... ... !!! ... ... |

##### input

1 2 3 4 5 6 7 8 9 10 11 12 |
xoo x.. x.. ooo ... ... ooo ... ... x.. x.. x.. ... ... ... ... ... ... x.. x.. x.. ... ... ... ... ... ... 7 4 |

##### output

1 2 3 4 5 6 7 8 9 10 11 |
xoo x!! x!! ooo !!! !!! ooo !!! !!! x!! x!! x!! !!! !!! !!! !!! !!! !!! x!! x!! x!! !!! !!! !!! !!! !!! !!! |

##### input

1 2 3 4 5 6 7 8 9 10 11 12 |
o.. ... ... ... ... ... ... ... ... ... xxx ... ... xox ... ... ooo ... ... ... ... ... ... ... ... ... ... 5 5 |

##### output

1 2 3 4 5 6 7 8 9 10 11 |
o!! !!! !!! !!! !!! !!! !!! !!! !!! !!! xxx !!! !!! xox !!! !!! ooo !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! |

### Note

In the first test case the first player made a move to lower left cell of central field, so the second player can put a chip only to cells of lower left field.

In the second test case the last move was done to upper left cell of lower central field, however all cells in upper left field are occupied, so the second player can put his chip to any empty cell.

In the third test case the last move was done to central cell of central field, so current player can put his chip to any cell of central field, which is already occupied, so he can move anywhere. Pay attention that this state of the game is unreachable.

# C. Shockers

2 seconds

256 megabytes

standard input

standard output

Valentin participates in a show called “Shockers”. The rules are quite easy: jury selects one letter which Valentin doesn’t know. He should make a small speech, but every time he pronounces a word that contains the selected letter, he receives an electric shock. He can make guesses which letter is selected, but for each incorrect guess he receives an electric shock too. The show ends when Valentin guesses the selected letter correctly.

Valentin can’t keep in mind everything, so he could guess the selected letter much later than it can be uniquely determined and get excessive electric shocks. Excessive electric shocks are those which Valentin got after the moment the selected letter can be uniquely determined. You should find out the number of excessive electric shocks.

### Input

The first line contains a single integer *n* (1 ≤ *n* ≤ 10^{5}) — the number of actions Valentin did.

The next *n* lines contain descriptions of his actions, each line contains description of one action. Each action can be of one of three types:

- Valentin pronounced some word and didn’t get an electric shock. This action is described by the string “. w” (without quotes), in which “.” is a dot (ASCII-code 46), and
*w*is the word that Valentin said. - Valentin pronounced some word and got an electric shock. This action is described by the string “! w” (without quotes), in which “!” is an exclamation mark (ASCII-code 33), and
*w*is the word that Valentin said. - Valentin made a guess about the selected letter. This action is described by the string “? s” (without quotes), in which “?” is a question mark (ASCII-code 63), and
*s*is the guess — a lowercase English letter.

All words consist only of lowercase English letters. The total length of all words does not exceed 10^{5}.

It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn’t make correct guesses about the selected letter before the last action. Moreover, it’s guaranteed that if Valentin got an electric shock after pronouncing some word, then it contains the selected letter; and also if Valentin didn’t get an electric shock after pronouncing some word, then it does not contain the selected letter.

### Output

Output a single integer — the number of electric shocks that Valentin could have avoided if he had told the selected letter just after it became uniquely determined.

### Examples

##### input

1 2 3 4 5 6 |
5 ! abc . ad . b ! cd ? c |

##### output

1 |
1 |

##### input

1 2 3 4 5 6 7 8 9 |
8 ! hello ! codeforces ? c . o ? d ? h . l ? e |

##### output

1 |
2 |

##### input

1 2 3 4 5 6 7 8 |
7 ! ababahalamaha ? a ? b ? a ? b ? a ? h |

##### output

1 |

### Note

In the first test case after the first action it becomes clear that the selected letter is one of the following: *a*, *b*, *c*. After the second action we can note that the selected letter is not *a*. Valentin tells word “b” and doesn’t get a shock. After that it is clear that the selected letter is *c*, but Valentin pronounces the word *cd* and gets an excessive electric shock.

In the second test case after the first two electric shocks we understand that the selected letter is *e* or *o*. Valentin tries some words consisting of these letters and after the second word it’s clear that the selected letter is *e*, but Valentin makes 3 more actions before he makes a correct hypothesis.

In the third example the selected letter can be uniquely determined only when Valentin guesses it, so he didn’t get excessive electric shocks.

# F. Power Tower

4.5 seconds

256 megabytes

standard input

standard output

Priests of the Quetzalcoatl cult want to build a tower to represent a power of their god. Tower is usually made of power-charged rocks. It is built with the help of rare magic by levitating the current top of tower and adding rocks at its bottom. If top, which is built from *k* - 1 rocks, possesses power *p* and we want to add the rock charged with power *w*_{k} then value of power of a new tower will be {*w*_{k}}^{p}.

Rocks are added from the last to the first. That is for sequence *w*_{1}, …, *w*_{m} value of power will be

*m*. Priests have

*n*rocks numbered from 1 to

*n*. They ask you to calculate which value of cumulative power will the tower possess if they will build it from rocks numbered

*l*,

*l*+ 1, …,

*r*.

### Input

First line of input contains two integers *n* (1 ≤ *n* ≤ 10^{5}) and *m* (1 ≤ *m* ≤ 10^{9}).

Second line of input contains *n* integers *w*_{k} (1 ≤ *w*_{k} ≤ 10^{9}) which is the power of rocks that priests have.

Third line of input contains single integer *q* (1 ≤ *q* ≤ 10^{5}) which is amount of queries from priests to you.

*k*^{th} of next *q* lines contains two integers *l*_{k} and *r*_{k} (1 ≤ *l*_{k} ≤ *r*_{k} ≤ *n*).

### Output

Output *q* integers. *k*-th of them must be the amount of cumulative power the tower will have if is built from rocks *l*_{k}, *l*_{k} + 1, …, *r*_{k}.

### Example

##### input

1 2 3 4 5 6 7 8 9 10 11 |
6 1000000000 1 2 2 3 3 3 8 1 1 1 6 2 2 2 3 2 4 4 4 4 5 4 6 |

##### output

1 2 3 4 5 6 7 8 |
1 1 2 4 256 3 27 597484987 |

### Note

3^{27} = 7625597484987

# Questions about problems

# | Party | When | Question | Answer |
---|---|---|---|---|

2017-12-23 18:02:19 | Announcement |
Problem C. Shockers ***** There was a mistake in description of first sample test case. Instead of “Valentin makes a hypothesis about the letter b and gets an electric shock.” you there should be “Valentin tells word b and doesn’t get a shock”. |
||

2017-12-23 17:18:12 | Announcement |
Problem C. Shockers ***** To make it clear: jury chooses only one hidden letter. |

### 907A – Masha and Bears

Sizes of cars should satisfy the following constraints:

- in
*i*-th car, Masha and corresponding bear are able to get into, so size of the car should not be less than*max*(*V*_{i},*V*_{m}); - each bear likes its car, so size of
*i*-th car is no more than 2·*V*_{i}; - Masha doesn’t like first two cars, then their sizes are more than 2·
*V*_{m}; - Masha likes last car, so it’s size is not more than 2·
*V*_{3}; - Sizes of cars are strictly ordered. It means that size of father’s car is strictly more than size of mother’s one, and size of mother’s car is strictly more than son’s car.

Sizes of bears don’t exceed 100; then, sizes of cars does not exceed 200, and there are only 200^{3} possible variants of sizes of cars. In given constraints, one can just go through all possible triples of sizes and check if each of them satisfies the constrains above or not.

### 907B – Tic-Tac-Toe

Let us describe each cell of the field by four numbers (*x*_{b}, *y*_{b}, *x*_{s}, *y*_{s}), 0 ≤ *x*_{b}, *y*_{b}, *x*_{s}, *y*_{s} ≤ 2), where (*x*_{b}, *y*_{b}) are coordinates of small field containing the cell, and (*x*_{s}, *y*_{s}) are coordinates of the cell in it’s small field. It can be seen that for cell with “usual” coordinates (*x*, *y*), 1 ≤ *x*, *y* ≤ 9 and our new (*x*_{b}, *y*_{b}, *x*_{s}, *y*_{s}), there are following equalities which give us a key to go between coordinate systems:

*x*_{b}= ⌊((*x*- 1) / 3)⌋,*y*_{b}= ⌊((*y*- 1) / 3)⌋;*x*_{s}= (*x*- 1)*mod*3,*y*_{b}= (*y*- 1)*mod*3;*x*= 3 **x*_{b}+*x*_{s}+ 1,*y*= 3 **y*_{b}+*y*_{s}+ 1.

In terms of new coordinates, if last move was in cell (*x*_{b}, *y*_{b}, *x*_{s}, *y*_{s}), then next move should be in arbitrary free cell with coordinates (*x*_{s}, *y*_{s}, *x*‘, *y*‘) for some if it’s possible; otherwise, next move can be done in arbitrary free cell. To solve the problem, one can go through all such pairs (*x*‘, *y*‘) and write “!” in each empty cell (*x*_{s}, *y*_{s}, *x*‘, *y*‘); if there are not such empty cells, write “!” in all empty cells of the field.

### 906A – Shockers

From last action, selected letter can be found; let it be *c* (without loss of generality). For each of other 25 letters, answers on some actions are contradicting with assumption that this letter was selected; moreover, for each letter *d* not equal to *c*, we can find the earlest such action with number *A*_{d} (for each action, we can easily check if assumption “*d* is selected” is contradicting with the action or not on linear time). Then, the answer is a number of electric shocks after action with number which is maximal among all such *A*_{d}-s.

### 906B – Seating of Students

The problem has many solutions, including random ones. Consider one of deterministic solutions. Without loss of generality, assume that *n* ≤ *m*.

There are a couple of corner cases:

*n*= 1,*m*= 1. In this case, good seating exists.*n*= 1,*m*= 2. In this case, seating does not exist (obviously).*n*= 1,*m*= 3. In any seating, one of neighbours of student 2 will be one of his former neighbours, so correct seating does not exist.*n*= 2,*m*= 2. Only student 4 can be a neighbour of student 1, but there should be 2 neighbours for student 1; then, correct seating does not exist.*n*= 2,*m*= 3. Both students 5 and 2 have 3 neighbours in the initial seating; then, in new seating, these students should be in non-neighbouring corner cells. Moreover, these corner cells can not be in one row because in this case it’s impossible to find a student for cell between 2 and 5. So, without loss of generality, let 5 be in lower left corner, and 2 — in upper right corner. Then, only students 1 and 3 can seat on lower middle cell; but if sduent 1 seats in the cell, then student 4 is impossible to seat at any of the remaining cells, so do student 6 in case of student 3 seating at the cell. So, correct seating does not exist in this case too.*n*= 1,*m*= 4. In this case, one of correct seatings is 2 4 1 3.*n*= 1;5 ≤*m*. In this case, let students with odd numbers in increasing order will be in first half of the row, and others in increasing order – in second half. For example, for*m*= 7 the seating will be 1 3 5 7 2 4 6.*n*=*m*= 3. One of possible correct seatings is:6 1 87 5 3

2 9 4;

- If 2 ≤
*n*;4 ≤*m*, then shift each even row cyclically on two symbols in the right, and then shift each even column cyclically on one symbol upwards. If students are vertical neighbours in the initial seating, then in new seating, they will be in different columns on the distance 2 (possibly through the edge of the table); but if students are horizontal neighbours in the initial seating, then in new seating they will be in neighbouring rows and neighbouring columns (possibly thorugh the edges again). So, for case 2 ≤*n*, 4 ≤*m*, we build a correct seating.

### 906C – Party

Let’s formulate and prove several facts.

1. If we change an call order, the result doesn’t change. Let’s consider two vertices which are called consecutively. If they are not connected by edge, then regardless of the order, we get that at the end, neighbours of each vertex form a clique.

If they are connected, then independently on the order, we get clique from 2 vertices and all neighbours of them.

2. If graph is a tree, it’s sufficient to take as an answer all its vertices except leaves. Indeed, if we consider any 2 tree vertices, we get that all vertices on the way between them are in the answer. Each vertex reduces on 1 the distance between those 2, it means that the distance between them is 1.

3. Let’s select from source graph spanning tree, that has the largest number of leaves. One can say that we can use all vertices except leaves as an answer.

Obviously from point 2, that after all our operations with such set graph will become complete. Let’s show that it is minimal number of vertices.

Let we selected some set of vertices, that is the answer. Then subgraph of given graph, built on the selected set of vertices, should be connected (otherwise between connected component can’t appear the edge and graph can’t be complete. Also, each of vertices, that isn’t in an answer should have at least one of neighbours selected (otherwise it is impossible to add new edge to it). Now let’s select a spanning tree in selected set (it’s possible because our set is connected) and add non-selected vertices into the tree as leafs. Then we see that our selected can be represented as spanning tree in the initial graph, in which all selected vertices are all non-leaf vertices and possibly, some leafs; but leafs can be obviously removed from the selected set by proved above. So, one of optimal answers can be described as set of non-leaf vertices of spanning tree with minimal possible number of non-leaves and, as a consequence, with maximal possible number of leaves, QED.

4. Implementation. It is necessary to implement an algorithm that should work for 2^{n}·*n* or faster or with worse asymptotic but with non-asymptotical optimization. One of possible solutions is following. Let contain any subset of vertices as a *n*-bit mask; for example, mask of a subset containing vertices {*v*_{1}, *v*_{2}, …, *v*_{k}} will be equal to 2^{v}_{1} + 2^{v}_{2} + … + 2^{v}_{k}. Then, for subset with mask *m*, vertex *v* is in set iff *m* & 2^{v} is not equal to 0; here & is a bitwise AND.

Let for each vertex *v*, *neighbours*[*v*] be a mask of subset of vertices containing vertex *v*and it’s neighbours. Array *neighbours*[*v*] can be calculated easily. Then, let *bool* *isConnected*[*m*] be 1 for some mask *m* iff subset coded by *m* is connected. Array *isConnected* can be calculated in *O*(2^{n} * *n*) by the following algorithm:

- for all vertices (let vertices be enumerated in 0-indexation),
*isCalculated*[2^{v}] is assigned to 1; for all other masks,*isCalculated*should be equal to 0; - then, go through all masks in increasing order by a simple cycle; let
*m*be current mask in the cycle; - if
*isConnected*[*m*] = 0, then go to the next iteration of cycle; - otherwise, let
*v*_{1},*v*_{2}, …,*v*_{k}be vertices of subset coded by*m*. Then, mask*m*‘: =*maskNeighbours*[*m*]: =*neighbours*[*v*_{1}]|*neighbours*[*v*_{2}]|… |*neighbours*[*v*_{k}]for | as bitwise OR is a mask coding a subset of vertices containing vertices of mask*m*and their neighbours. Then, for each vertex*w*in subset of mask*m*‘ we assign*isConnected*[*m*|2^{w}] to be 1.

The described algorithm works in *O*(2^{n} * *n*); it can be proved by induction that at the end, *isConnected*[*m*] = 1 for mask *m* iff *m* is a code of connected subset of vertices.

But how to find an answer? Notice that mask *m* = 2^{v}_{1} + 2^{v}_{2} + … + 2^{v}_{k} is a code of good (for our purposes) subset iff *isConnected*[*m*] = 1 and *maskNeighbours*[*m*] = 2^{n} - 1 = 2^{0} + 2^{1} + … + 2^{n - 1}. For each mask *m*, we can check if it’s good in *O*(*n*) time having an array *isConnected* calculated; the answer is a good mask with minimal possible number of elements in the corresponding set.

### 906D – Power Tower

Let’s learn to calculate . Assume that we want to find where *n* and *m* non necessary co-prime, and *x* is some big number which we can calculate only modulo some value.

We can solve this problem for co-prime *n* and *m* via Euler’s theorem. Let’s reduce general case to that one. Note that . Indeed if *n* = *d*·*m* + *r*, |*r*| < *m*, then *an* = *d*·*am* + *ar*, |*ar*| < |*am*|. Let *p*_{1}, …, *p*_{t} to be common prime divisors of *n* and *m*, *a* = *p*_{1}^{k1}… *p*_{t}^{kt} to be such number that it divisible by such divisors to the power they occur in *m*, and *k* to be least number such that . Then we have a chain

*n*and

*m*/

*a*are co-prime so we can calculate power value module . Moreover, , thus case

*x*<

*k*can be considered in .

This is already enough to solve the problem, but continuing one can prove that for it holds

*m*) is Euler totient function of

*m*. Finally, to solve the problem one shoud note that so it will take only steps before

*m*turns into 1.

### 906E – Reverses

After inverses we have transform . Consider operator for strings of equal lengths. Under such operator string will turn into where *X*_{k} is string which has all characters doubled and *Y*_{k} is arbitrary palindrome of even length.

Let’s move through letters from left to right and keep minimum number on which we can split current prefix. Last letter will either be in some palindrome or is doubled. For doubled letters we consider *ans*_{i} = *min*(*ans*_{i}, *ans*_{i - 2}). As for palindromes of even length, one can fit standard algorithm of splitting string into the minimum number of palindromes in such way that it will consider only splittings on even palindromes. For example, one can consider only such spits that every palindrome in the split end up in even index.