First change all the letters into lower case ones, and then compare the two strings as the problem requires.

To cut the whole board into two symmetric parts, the cutting line must pass through the central point. Therefore, the following four squares can not be special cells, i.e., (*n*, *n* + 1), (*n*, *n*), (*n* + 1, *n*), (*n* + 1, *n* + 1), where (*r*, *c*) denotes the *r*-th row and the *c*-th column.

I did not figure out how to prove this, however it turns out that the following solution can pass all the tests.

At first, note that if can satisfy the requirement, then can satisfy as well. Thus, we set *a*_{1} = *a*_{2} = ...*a*_{n - 1} = 1 and *a*_{n} = *y* - *n* + 1, which gives the maximum value of . Moreover, if *y* < *n*, then the answer is definitely “-1”; otherwise we divide *y* as mentioned above and check the result is no less than *x* or not.

For each integer *n*, it takes complexity to obtain all its divisors. For each divisor, we should check whether it is divisible by any one of the previous *y* integers. Thus, we can use an array *idx*[*n*] to record the maximum index of the given integer that has *n* as its divisor. When we deal with the current *i*-th query, we find out each of its divisor *x*, and check *idx*[*x*] to determine whether this divisor satisfies the requirement or not. Next, we update *idx*[*x*] = *i*, since *x* is divisible by the *i*-th integer.

**Update-1**: proof of 112C - Petya and Inequiations

Given *a*_{1} + *a*_{2} + ... + *a*_{n} = *D* where only positive integers are involved and *D* ≥ *n*, the maximum value of *a*_{1}^{2} + *a*_{2}^{2} + ... + *a*_{n}^{2} is (*n* - 1) + (*D* - (*n* - 1))^{2} with *a*_{1} = *a*_{2} = ... = *a*_{n - 1} = 1 and *a*_{n} = *D* - (*n* - 1), i.e., the optimal sequence can have at most one positive integer that is greater than 1.

Proof: We prove this claim by contradiction. Assume that the optimal sequence has more than one positive integer that is greater than 1, and we denote them as *x* and *y*, with *x* > 1 and *y* > 1. Then, we write *s*_{1} = *x*^{2} + *y*^{2} and *s*_{2} = 1^{2} + (*y* + *x* - 1)^{2}, and one can see that the term *s*_{2} means that we set *x* = 1 while "moving" a quantity of *x* - 1 to *y*. Next, *s*_{2} - *s*_{1} = 1 + (*y* + *x* - 1)^{2} - *x*^{2} - *y*^{2} = 1 - *y*^{2} + (*y* - 1)(*y* + 2*x* - 1) = (*y* - 1)(*y* + 2*x* - 1) - (*y* - 1)(*y* + 1) = 2(*y* - 1)(*x* - 1) > 0. Thus, we have obtained a larger (better) value since *s*_{2} > *s*_{1} and this is contradictory to our assumption, which completes the proof.