You are given a sequence $\textbf{a}$ denoted by $(a_1, a_2, \cdots, a_n)$. A query with $1 \leq l \leq r \leq n$ is defined as
$Q_{max}(l, r) = \max\lbrace a_l, a_{l + 1}, \cdots, a_r\rbrace$.
An easy problem may ask you to calculate the sum of answers for all queries with integers $1 \leq l \leq r \leq n$, but we would like to show you a harder one.

Define a classifier as a container that stores unique elements. Each element in the classifier has two values, named the key value and the mapped value. The key value of each element is a consecutive subsequence of $\textbf{a}$ and the mapped value of that element is an integer indicating the maximum value in the subsequence. The classifier only stores elements with distinct key values, which means extra duplicated elements (with the same key value) would be removed from the classifier.

Denote $S(l, r)$ as $(a_l, a_{l + 1}, \cdots, a_r)$, a consecutive subsequence of $\textbf{a}$ meeting the condition that $l$ and $r$ are integers with $1 \leq l \leq r \leq n$. Now we intend to use a classifier $\textbf{CA}$ to store all the consecutive subsequences $S(l, r)$ of $\textbf{a}$ with their $Q_{max}(l, r)$. You are asked to determine the sum of mapped values in $\textbf{CA}$.

Actually, what we defined above is a map of the form map<vector<int>, int> in C++ or Map<ArrayList<Integer>, Integer> in Java, so if you are seasoned using these data structures, you may realize that what we intend to do is to insert all possible elements $(S(l, r), Q_{max}(l, r))$ with integers $1 \leq l \leq r \leq n$ into the classifier $\textbf{CA}$ and then ask you to calculate the sum of mapped values in it.

As we know, DreamGrid is a master of planning algorithm. Recently, a new type of autonomous car appears in Gridland. With the shape of a circle, the car can move in any direction. Being interested in this car, DreamGrid decides to design a specific path planning algorithm for it. Here is the first case he wants to solve.

Consider two cars on the two-dimensional plane with the same radius of $r$. We now want to move the center of the first car from $(0, 0)$ to $(d, 0)$, where $d$ is positive. The second car, starting its move with its center located at $(2r, 0)$, can be considered as an obstacle moving towards the positive direction of the x-axis with a constant speed of $v$. Luckily, after installing a new engine, the first car can move twice as fast as the obstacle car, which means the maximum speed of the first car can be $2v$.

DreamGrid wants to know the shortest time needed to move the first car to the end point without colliding with the second car. That is to say, before arriving at the end point, the circle representing the first car can’t intersect with (but can be tangent to) the circle representing the second car.

As DreamGrid is too busy, you are asked to solve this simple problem for him. Of course, if you successfully solve this problem, you will get a brand-new autonomous car in the Gridland!

Morgana is learning Convolutional Neural Network, he builds a neural network called “morgana net”.

In brief, given a $N \times N$ matrix $A$ that represents a picture. Every layer in morgana net is doing work as follow:

$$\displaystyle A_{k+1}[i][j] = f(\sum_{p = i - m}^{i + m}\sum_{q = j - m}^{j + m} A_k[p][q]\ B[p - i + m + 1][q - j + m + 1])$$

Every layer can be represented by a $N \times N$ matrix $A_k$​ and $A_k$​ means it is the $k$th layer. $B$ is the $(2m+1) \times (2m+1)$ matrix represents convolution kernel. And if $(p, q)$ are out of $A$, $A[p][q]$ will be $0$ (if $p \le 0$ or $q \le 0$ or $p > n$ or $q > n$). $f(x)$ is the activation function and in morgana net $f(x) = x \mod 2$.

Now morgana gives you the input $A_0$​ represents a picture, he wants to know after ttt layers, how many nerve cells’ value are equal to $1$ . (that means how many elements in At are equal to $1$).

Shinku is very interested in the set. One day, she got $n$ sets, and the $i$-th number $a_i$​ is in the $i$-th set. But she doesn’t think it is interesting enough, so she applies mmm magic to these sets. There are three kinds of magic:

1 $1\ u\ v$: If the uuu-th and $v$-th numbers are not in one set, then the Shinku’s magic will merge the set containing the $u$-th number and the set containing the $v$-th number.

2 $2\ u$: Shinku’s magic adds $1$ to each number in the set containing the $u$-th number.

3 $3\ u\ k\ x$: Shinku can immediately know how many numbers $t$ in the set containing the $u$-th number satisfy $t\equiv x (\bmod\ 2^k)(0 \le k\le 30,0\le x<2^k)$.

But unfortunately, for some reason the type $3$ magic fails. So Shinku wants you to tell her the answer after every type $3$ magic.

Note that there can be multiple numbers with the same value in one set, that is, numbers with the same value will not disappear when merged.

Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough.

Suppose the shell necklace is a sequence of shells (not a chain end to end). Considering i continuous shells in the shell necklace, I know that there exist different schemes to decorate the i shells together with one declaration of love.

I want to decorate all the shells with some declarations of love and decorate each shell just one time. As a problem, I want to know the total number of schemes.

You are given a tree. If we select 2 distinct nodes uniformly at random, what’s the probability that the distance between these 2 nodes is a prime number?

You have $N$ integers $A_1, A_2, … , A_N$. You are asked to write a program to receive and execute two kinds of instructions:

1. C a b means performing $A_i = (A_i^2 \mod 2018)$ for all $A_i$ such that $a ≤ i ≤ b$.
2. Q a b means query the sum of $A_a, A_{a+1}, …, A_b$. Note that the sum is not taken modulo $2018$.

Recently George is preparing for the Graduate Record Examinations (GRE for short). Obviously the most important thing is reciting the words.
Now George is working on a word list containing N words.
He has so poor a memory that it is too hard for him to remember all of the words on the list. But he does find a way to help him to remember. He finds that if a sequence of words has a property that for all pairs of neighboring words, the previous one is a substring of the next one, then the sequence of words is easy to remember.
So he decides to eliminate some words from the word list first to make the list easier for him. Meantime, he doesn’t want to miss the important words. He gives each word an importance, which is represented by an integer ranging from -1000 to 1000, then he wants to know which words to eliminate to maximize the sum of the importance of remaining words. Negative importance just means that George thought it useless and is a waste of time to recite the word.
Note that although he can eliminate any number of words from the word list, he can never change the order between words. In another word, the order of words appeared on the word list is consistent with the order in the input. In addition, a word may have different meanings, so it can appear on the list more than once, and it may have different importance in each occurrence.

As an eligible Ingress Resistance Agent you should know your power source, the Exotic Matter.
We call it XM, which is the driving force behind all of our actions in Ingress.
XM allows us to construct items through hacking portals, to attack enemy portals, make links and create fields.

We try to collect XM from the ground. XM concentration come from location based services, meaning that areas with a lot of foot traffic have higher amounts versus places that don’t.
You can collect XM by moving through those areas.
The XM will be automatically harvested by your Scanner when it is within your interaction circle/range.

Alice decides to select a location such that she can collect XM as much as possible.
To simplify the problem, we consider the city as a grid map with size ‘$n * m$’ numbered from $(0,0)$ to $(n-1,m-1)$.
The XM concentration inside the block $(i,j)$ is $p(i,j)$.
The radius of your interaction circle is $r$.
We can assume that XM of the block $(i,j)$ are located in the centre of this block.
The distance between two blocks is the Euclidean distance between their centres.

Alice stands in the centre of one block and collects the XM.
For each block with the distance $d$ smaller than $r$ to Alice, and whose XM concertation is $p(i,j)$, Alice’s scanner can collects $p(i,j)/(1+d)$ XM from it.

Help Alice to determine the maximum XM which she can collect once he stands in the centre of one block.