B'Fedya has a string S , initially empty, and an array W , also initially empty. There are n queries to process, one at a time. Query i consists of a lowercase English letter c_i and a nonnegative integer w_i . First, c_i must be appended to S , and w_i must be appended to W . The answer to the query is the sum of suspiciousnesses for all subsegments of W [L, R] , (1 <= q L <= q R <= q i) . We define the suspiciousness of a subsegment as follows: if the substring of S corresponding to this subsegment (that is, a string of consecutive characters from L -th to R -th, inclusive) matches the prefix of S of the same length (that is, a substring corresponding to the subsegment [1, R - L + 1] ), then its suspiciousness is equal to the minimum in the array W on the [L, R] subsegment. Otherwise, in case the substring does not match the corresponding prefix, the suspiciousness is 0 . Help Fedya answer all the queries before the orderlies come for him! The first line contains an integer n (1 <= q n <= q 600 ,000) -- the number of queries. The i -th of the following n lines contains the query i : a lowercase letter of the Latin alphabet c_i and an integer w_i (0 <= q w_i <= q 2^{30} - 1) . All queries are given in an encrypted form. Let ans be the answer to the previous query (for the first query we set this value equal to 0 ). Then, in order to get the real query, you need to do the following: perform a cyclic shift of c_i in the alphabet forward by ans , and set w_i equal to w_i oplus (ans & MASK) , where oplus is the bitwise exclusive "or", & is the bitwise "and", and MASK = 2^{30} - 1 . Print n lines, i -th line should contain a single integer -- the answer to the i -th query. For convenience, we will call "suspicious" those su'...