It is obvious that all the digits, which are greater than 4, need to be inverted. The only exception is 9, if it's the first digit.
Let's run through every point, where the stormtroopers are situated. If in current point stormtroopers are still alive, let's make a shot and destroy every stormtrooper on the same line with gun and current point.
Points (x 1, y 1), (x 2, y 2), (x 3, y 3) are on the same line, if (x 2 - x 1)(y 3 - y 1) = (x 3 - x 1)(y 2 - y 1).
While adding a string to the set, let's count its polynomial hash and add it to an array. Then let's sort this array. Now, to know the query answer, let's try to change every symbol in the string and check with binary search if its hash can be found in the array (recounting hashes with complexity). If the hash is found in the array, the answer is "YES", otherwise "NO".
Complexity: , where L is total length of all strings.
To destroy all the droids on a segment of l to r, we need to make shots, where cnt[i][j] — number of j-type details in i-th droid. Let's support two pointers — on the beginning and on the end of the segment, which we want to destroy all the droids on. If we can destroy droids on current segment, let's increase right border of the segment, otherwise increase left border, updating the answer after every segment change. Let's use a queue in order to find the segment maximum effectively.
It's easy to realize that , where dp[i] is number of vertices, which are situated on a distance i from the root, and cnt[j] is number of children, which are situated on a distance j. Answer .
Let the dynamics condition
Let's build a transformation matrix of 101 × 101 size
Now, to move to the next condition, we need to multiply A by B. So, if matrix C = A·B x - 100, then the answer will be situated in the very right cell of this matrix. For x < 100 we'll find the answer using dynamics explained in the beginning.
In order to find B k let's use binary power.