There are $$$n$$$ SWERC candidates in USI and we are going to hold a contest for them. Each of the candidates has a consecutive free period to do the contest. For the $$$i$$$-th candidate, he/she is available from the $$$l_i$$$-th slot to $$$r_i$$$-th slot. The question is, is there a slot that everyone is free so we can do the contest at that time?

Boboge is currently at $$$(x_1, y_1)(y_1 \gt 0)$$$, there is a river at $$$y=0$$$, and his destination is at $$$(x_2, y_2)(y_2 \gt 0)$$$. He needs to get some water from the river first, then go to the destination. What's the minimum distance he has to travel?

A example.

jiangly is pretty good at competitive programming.

Now, there are $$$n$$$ professors, each giving a grade for jiangly's competitive programming skills. The $$$i$$$-th professor gives a grade of $$$a_i$$$.

If we sort all the grades and delete the first and the last ones (minimum and maximum), the sum of the rest grades would be the final grade for jiangly. Formally, if array $$$b$$$ are the sorted grades, the final grade is:

$$$$$$ \sum_{i=2}^{n-1}{b_i} $$$$$$

If you talk to some professor about this fact, the grade this professor will give to jiangly would rise a little bit. If you talk to $$$i$$$-th professor, $$$a_i$$$ will becomes to $$$d_i(a_i \lt d_i)$$$.

You do not have much time, so you can only talk to one professor about the fact.

As you want the grade to be fair, you want to maximize jiangly's grade. Note that we sort the grades after you talk to a professor.

You are given an array of length $$$n$$$ consisting of positive integers that do not exceed $$$m$$$.

You have $$$2^n - 1$$$ ways to choose a non-empty subsequence of the array.

For each $$$x \in [1, m]$$$, how many ways you can choose a non-empty subsequence $$$b$$$ of $$$a$$$ that:

$$$$$$ gcd(b_1, b_2, ...) = x $$$$$$

The greatest common divisor $$$gcd(a,b,c, \dots)$$$ of multiple positive integers is equal to the biggest integer $$$d$$$ such that all integers $$$a,b,c,\dots$$$ are divisible by $$$d$$$.

You have to print the answer for every $$$x$$$, since the answer could be huge, print the answer taken modulo $$$998244353$$$. If you get the same subsequence with different choices, they are considered to be different.

You are given a random generated tree rooted at $$$1$$$ with $$$n$$$ vertices and some queries. Here a tree is a connected graph in which there are no cycles.

Each vertex of the tree has a weight $$$W_i$$$.

Each query has $$$2$$$ vertices $$$(u, v)$$$. For each query, assume that array $$$a$$$ is the path from $$$1$$$ to $$$u$$$, and array $$$b$$$ is the path from $$$1$$$ to $$$v$$$, find $$$2$$$ subsequence with equal length from $$$a$$$ and $$$b$$$ respectively as $$$c$$$ and $$$d$$$, maximize the following value:

$$$$$$ \sum_{i=1}^{size_c} W_{c_i} \times W_{d_i} $$$$$$

The tree itself is generated as follows:

Generate_tree(n):
    for i := 2 -> n
        father[i] := random choose an integer from [1, i - 1]
    return father

p.s. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

You are given an array $$$a$$$ with length $$$n$$$.

To make an array beautiful, you must make it as short as possible. What you can do is choose a pair of adjacent elements, provided they are different. After you delete the pair, there may be a new pair that becomes adjacent. e.g. If you delete $$$a_2$$$ and $$$a_3(a_2 \neq a_3)$$$, $$$a_1$$$ and $$$a_4$$$ will become adjacent. After the removals, the minimum length of the array can be achieved is the beauty of the original array.

For example, the beauty of the array $$$[1, 1, 2, 2]$$$ is $$$0$$$, as you can delete element in position $$$2$$$ and $$$3$$$, and the array becomes $$$[1, 2]$$$, then you can make it empty.

However, this could be too easy, so you are also given $$$q$$$ queries. Each query consists of two integers $$$(l,r)$$$, denotes that you need output the beauty of array $$$[a_l,a_{l+1},\dots,a_{r-1},a_r]$$$.