Sizes of cars should satisfy the following constraints:

1. 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);
2. each bear likes its car, so size of i-th car is no more than 2·V_i;
3. Masha doesn’t like first two cars, then their sizes are more than 2·V_m;
4. Masha likes last car, so it’s size is not more than 2·V₃;
5. 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³ 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.

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.

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.

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:

1. n = 1, m = 1. In this case, good seating exists.
2. n = 1, m = 2. In this case, seating does not exist (obviously).
3. 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.
4. 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.
5. 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.
6. n = 1, m = 4. In this case, one of correct seatings is 2 4 1 3.
7. 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.
8. n = m = 3. One of possible correct seatings is:6 1 8

   7 5 3

   2 9 4;

9. 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.

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 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₁, v₂, …, v_k} will be equal to 2^v₁ + 2^v₂ + … + 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 vand 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) 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₁, v₂, …, v_k be vertices of subset coded by m. Then, mask m‘:  = maskNeighbours[m]:  = neighbours[v₁]|neighbours[v₂]|… |neighbours[v_k]for | as bitwise OR is a mask coding a subset of vertices containing vertices of mask mand 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); 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₁ + 2^v₂ + … + 2^v_k is a code of good (for our purposes) subset iff isConnected[m] = 1 and maskNeighbours[m] = 2ⁿ - 1 = 2⁰ + 2¹ + … + 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.

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₁, …, p_t to be common prime divisors of n and m, a = p₁^k₁… p_t^k_t 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

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

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.