A string $$$s$$$ is beautiful if it can be expressed in the form:

$$$$$$s=t+t'+t$$$$$$

where:

• $$$+$$$ is defined as the concatenation of strings;
• $$$t$$$ is a non-empty string;
• $$$t'$$$ is the reverse of $$$t$$$.

You are given a string $$$s$$$. Find the number of beautiful substrings of $$$s$$$.

You are given a positive integer $$$N$$$ and a digit $$$x$$$ ($$$1 \le x \le 9$$$). Let $$$n$$$ be the number of digits of the decimal representation of $$$N$$$. For example, if $$$N=10000$$$, then $$$n=5$$$; if $$$N=114514$$$, then $$$n=6$$$.

Define $$$g(M)$$$ to be the number of occurrences of the digit $$$x$$$ in the decimal representation of $$$M$$$. For example, if $$$x=6$$$, then $$$g(1)=0$$$, $$$g(666)=3$$$, and $$$g(16161)=2$$$.

For each integer $$$k$$$ with $$$0 \le k \le n$$$, let $$$f(k)$$$ be the number of positive integers $$$M \le N$$$ for which $$$g(M)=k$$$.

Your task is to compute $$$f(k) \bmod {998244353}$$$ for every $$$0 \le k \le n$$$.

You are given a graph of $$$n$$$ vertices labeled from $$$1$$$ to $$$n$$$, initially with no edges. You need to process $$$q$$$ queries of the following types:

• $$$1~u~v$$$: add an undirected edge between vertices $$$u$$$ and $$$v$$$.
• $$$2~l~r$$$: for each pair of integers $$$(x,y)$$$ such that $$$l \le x \lt y \le r$$$, add an undirected edge between vertices $$$x$$$ and $$$y$$$.

After each query, output the number of pairs of integers $$$(x,y)$$$ such that $$$1 \le x \lt y \le n$$$ and there exists a path from vertex $$$x$$$ to vertex $$$y$$$. A path from vertex $$$x$$$ to vertex $$$y$$$ is defined as a sequence of integers $$$p_1,p_2,\ldots,p_m$$$ such that $$$p_1=x$$$, $$$p_m=y$$$, and there exists an undirected edge between vertices $$$p_i$$$ and $$$p_{i+1}$$$ for all $$$1 \le i \lt m$$$.

Note that you must solve this problem in online mode. That is, you can only read the current query after outputting the answer for the previous one. Also, remember to flush the output after each query. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

You are given an array $$$a$$$ of length $$$n$$$. Your task is to process $$$q$$$ queries of three types:

• $$$1~i~x$$$ — set $$$a_i:=x$$$.
• $$$2~l~r~x$$$ — for each $$$i$$$ such that $$$l \le i \le r$$$, set $$$a_i:=\gcd(a_i,x)$$$, where $$$\gcd(x,y)$$$ represents the largest integer that divides both $$$x$$$ and $$$y$$$.
• $$$3~l~r$$$ — compute $$$\sum_{i=l}^ra_i$$$.

Output the answer for each type $$$3$$$ query.

Note: this problem is different from "WTF Another GCD?". The difference is highlighted in bold.

In this task, you need to maintain a multiset $$$S$$$ that stores pairs of integers $$$(v,w)$$$.

Your multiset should support $$$n$$$ operations of the following types:

• + v w: insert a pair $$$(v,w)$$$ into $$$S$$$.
• - v w: remove a pair $$$(v,w)$$$ from $$$S$$$. It is guaranteed that $$$(v,w)$$$ exists in $$$S$$$. If there are multiple occurrences of the pair, remove only one occurrence.
• ? k: This is a query. Find a pair $$$(v,w)$$$ in $$$S$$$ such that $$$v$$$ and $$$k$$$ are not coprime, and $$$w$$$ is maximised. You only need to output the value of $$$w$$$. More formally, find:

  $$$$$$\max(\{w~|~(v,w) \in S \land \gcd(v,k) \ne 1 \})$$$$$$

  where $$$\gcd(x,y)$$$ represents the largest integer that divides both $$$x$$$ and $$$y$$$.

  If no such pair exists, output $$$0$$$.

Note: this problem is different from "Another GCD". The difference is highlighted in bold.

In this task, you need to maintain a multiset $$$S$$$ that stores pairs of integers $$$(v,w)$$$.

Your multiset should support $$$n$$$ operations of the following types:

• + v w: insert a pair $$$(v,w)$$$ into $$$S$$$.
• - v w: remove a pair $$$(v,w)$$$ from $$$S$$$. It is guaranteed that $$$(v,w)$$$ exists in $$$S$$$. If there are multiple occurrences of the pair, remove only one occurrence.
• ? k: This is a query. Find a pair $$$(v,w)$$$ in $$$S$$$ such that $$$v$$$ and $$$k$$$ are coprime, and $$$w$$$ is maximised. You only need to output the value of $$$w$$$. More formally, find:

  $$$$$$\max(\{w~|~(v,w) \in S \land \gcd(v,k) = 1 \})$$$$$$

  where $$$\gcd(x,y)$$$ represents the largest integer that divides both $$$x$$$ and $$$y$$$.

  If no such pair exists, output $$$0$$$.

This is an interactive problem.

There is a hidden non-negative integer $$$n$$$ ($$$0 \le n \lt 2^{64}$$$). Your task is to determine $$$n$$$ by asking queries of the following type:

• Choose a non-negative integer $$$x$$$ ($$$0 \le x \lt 2^{64}$$$). The judge will respond with the number of set bits in the binary representation of $$$n \oplus x$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. The number of set bits of a non-negative integer $$$x$$$ is the number of $$$1$$$s in its binary representation. For example, the binary representation of $$$13$$$ is $$$1011$$$, hence the number of set bits is $$$3$$$.

You may ask no more than $$$63$$$ queries.

To ask a query, output a line in the following format:

• ? x

where $$$x$$$ ($$$0 \le x \lt 2^{64}$$$) is the integer you asked.

After each query, you should read one line containing one integer, denoting the number of set bits of $$$n \oplus x$$$.

When you are ready to output the answer, output a line in the following format:

• ! n

where $$$n$$$ ($$$0 \le n \lt 2^{64}$$$) is the hidden integer.

Note that printing the answer is not counted within the total number of queries.

The interactor is NOT adaptive, meaning that the answer is known before the participant asks the queries and does not depend on the queries asked by the participant.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

You are given a positive integer $$$n$$$. Construct a permutation $$$p$$$ of $$$\{1,2,\ldots,n\}$$$ such that the length of the longest increasing subsequence of $$$p$$$ is equal to the length of the longest decreasing subsequence of $$$p$$$.

An increasing (decreasing) subsequence of an array $$$a$$$ of length $$$n$$$ is defined as an array $$$b$$$ such that:

• $$$1 \le b_1 \lt b_2 \lt \ldots \lt b_m \le n$$$.
• $$$a_{b_1} \lt a_{b_2} \lt \ldots \lt a_{b_m}$$$ ($$$a_{b_1} \gt a_{b_2} \gt \ldots \gt a_{b_m}$$$).

Yes, this problem is related to squares.

You are given a set $$$S$$$ of $$$n$$$ distinct points on the $$$xy$$$-plane, each with integer coordinates. A set of points $$$T$$$ is squarish if it contains exactly four points, and they can form the four vertices of a square.

Now, you have to remove exactly one point from $$$S$$$. Find the maximum number of squarish subsets of $$$S$$$ if you remove the point optimally.

In case you are not aware, three squared equals nine.

The nuclear power plant (HDZ) on planet A has exploded, turning into ruins. The height of the ruins can be represented by a permutation $$$p$$$ of $$$\{1,2,\ldots,n\}$$$, where the height at position $$$i$$$ is $$$p_i$$$.

Scientists have designed a robot named Bronya with a detection range $$$d$$$ to clean up nuclear waste at the highest point (height $$$n$$$) in the ruins. During airdrop, since precise positioning is impossible, Bronya may land at any position in the ruins. After landing, Bronya begins moving: if Bronya is at position $$$i$$$, she will move to the highest position $$$j$$$ such that $$$\max(1,i-d) \le j \le \min(n,i+d)$$$, repeating this process $$$10^{100}$$$ times. As a scientist, you need to determine the minimum $$$d$$$ such that no matter where Bronya lands initially, she will reach the highest point after all movements.

Baozii is bad at coming up with interesting stories for the problem statement, so he decided to present the problem to you straightaway.

You are given a tree $$$T$$$, consisting of $$$n$$$ vertices labeled from $$$1$$$ to $$$n$$$. Recall that a tree is a connected acyclic graph. There are $$$k$$$ stones on the tree, where the $$$i$$$-th stone is located at vertex $$$a_i$$$. In each operation, you can move a stone to one of its neighbouring vertices. Note that having multiple stones on one vertex is allowed.

A path from vertex $$$u$$$ to vertex $$$v$$$ is defined as a sequence of distinct vertices $$$p_1,p_2,\ldots,p_m$$$, such that $$$p_1=u$$$, $$$p_m=v$$$, and there exists an edge between vertices $$$p_i$$$ and $$$p_{i+1}$$$ for all $$$1 \le i \lt m$$$.

The tree is good if there exists a path such that all stones are located on the path. Note that the stones may not necessarily cover the entire path. They just have to be located at vertices on the path.

Your task is to compute the minimum number of operations required to make $$$T$$$ good.

For an array $$$a$$$, define $$$f(a)$$$ as follows:

• First, partition $$$a$$$ into two disjoint subsets $$$S_1$$$ and $$$S_2$$$ (could be empty), where each element belongs to exactly one subset.
• Calculate the bitwise OR of all elements in $$$S_1$$$. Let it be $$$v_1$$$. Particularly, $$$v_1 = 0$$$ if $$$S_1 = \emptyset$$$.
• Calculate the bitwise AND of all elements in $$$S_2$$$. Let it be $$$v_2$$$. Particularly, $$$v_2 = 0$$$ if $$$S_2 = \emptyset$$$.
• The score of this partition is $$$v_1+v_2$$$.
• $$$f(a)$$$ is defined as the maximum score over all possible partitions.

You are given an array $$$a$$$ of length $$$n$$$. Answer $$$q$$$ queries in the following form:

• $$$l~r$$$ ($$$1 \le l \le r \le n$$$): compute $$$f([a_l,a_{l+1},\ldots,a_r])$$$.

Baozii Cup problems have always been known for their succinct problem statements. This one is no exception.

You are given an array $$$a$$$ of length $$$n$$$. Count the number of quadruplets of integers $$$(i,j,k,l)$$$ that satisfy the following conditions:

• $$$1 \le i \lt j \lt k \lt l \le n$$$.
• $$$(a_i=a_k) \land (a_j=a_l) \land (a_i \ne a_j)$$$.