You are given an integer sequence $$$\{A_i\}$$$ of length $$$n$$$ and a line $$$y=kx+b$$$ denoted by two integers $$$k,b$$$.

We say that an integer radius $$$r$$$ of center $$$i$$$ is good if and only if $$$i+r\leq n$$$, $$$i-r \gt 0$$$, and $$$A_{i+r}-A_{i-r}=kr+b$$$. We define the $$$\text{rad}(i)$$$ as the maximum integer $$$r_0$$$ so that for every $$$1\leq r\leq r_0$$$, $$$r$$$ is a good radius of center $$$i$$$.

You need to process queries of two types:

• $$$1 \ l\ r\ v$$$: for every $$$l\leq i\leq r$$$, increase $$$A_i$$$ by $$$v$$$;
• $$$2 \ i$$$: calculate $$$\text{rad}(i)$$$.

For a multiset $$$S$$$ consisting of non-negative integers, let $$$p(S)$$$ denote the number of distinct sequences obtained by permuting the elements of $$$S$$$.

For example, if $$$S = \{1, 1, 2\}$$$, then there are three distinct sequences: $$$\{1, 1, 2\}$$$, $$$\{1, 2, 1\}$$$, and $$$\{2, 1, 1\}$$$, so $$$p(S) = 3$$$.

For non-negative integers $$$n, x, y$$$, let $$$f(n, x, y)$$$ be the number of multisets $$$S$$$ satisfying the following conditions: $$$|S| = n$$$, $$$\sum_{i \in S} i = x$$$, $$${\rm OR}_{i \in S} i = y$$$, and $$$p(S)$$$ is odd.

Now, given non-negative integers $$$n, x, y_{\max}$$$, calculate $$$f(n, x, y)$$$ for any subset $$$y$$$ of the binary representation of $$$y_{\max}$$$, modulo $$$10^9 + 7$$$.

Given a string $$$s$$$ of length $$$n$$$.

We say that a string $$$t$$$ is $$$\bf{mentioned}$$$ in $$$s$$$ if and only if there exist integers $$$l,r$$$, satisfying $$$1 \le l \le r \le n$$$, $$$\gcd(l, r) = 1$$$ and $$$s[l, r] = t$$$.

Here, $$$s[l, r]$$$ is defined as the string that is made by concatenating $$$s_l, s_{l+1}, \dots, s_r$$$, and $$$\gcd(l, r)$$$ represents the greatest common divisor of $$$l$$$ and $$$r$$$.

You should calculate the sum of the lengths of all distinct non-empty strings that are mentioned in $$$s$$$.

A sequence is good when it can be represented by several $$$\mathtt{()}$$$ connected together.

Formally, a sequence $$$s$$$ of length $$$2n$$$ is good when $$$s_1=s_3=\dots=s_{2n-1}=\mathtt{(}$$$ and $$$s_2=s_4=\dots=s_{2n}=\mathtt{)}$$$. In that case, we call $$$n$$$ its $$$\bf{depth}$$$.

Given a sequence $$$s$$$ of length $$$n$$$ which consists of $$$\mathtt{(}$$$ and $$$\mathtt{)}$$$. Let $$$f(l,r,k)$$$ be the number of good subsequences with depth $$$k$$$ in the sequence $$$t$$$ formed by $$$s_l,s_{l+1},\dots,s_r$$$.

You are given $$$q$$$ queries, each query contains four numbers $$$op,l,r,k$$$.

• If $$$op=1$$$, you need to calculate $$$f(l,r,k)$$$.
• If $$$op=2$$$, you need to calculate $$$\sum_{l\leq l'\leq r'\leq r}f(l',r',k)$$$.

Since the answer could be huge, you need to output the answer modulo $$$998244353$$$.

You're given a complete directed graph $$$G$$$ with $$$n$$$ vertices. We call a vertex $$$u$$$ dominating if for every $$$v\neq u$$$, there either exists an edge $$$(u\rightarrow v)$$$ or there exists a vertex $$$w$$$ satisfying $$$(u\rightarrow w)$$$ and $$$(w\rightarrow v)$$$.

You now need to find $$$3$$$ distinct dominating vertices of the given graph. If there are less than $$$3$$$ dominating vertices, output $$$\texttt{NOT FOUND}$$$.

You are given three integers $$$k$$$, $$$p$$$, $$$x$$$. Find the number of integer pairs $$$(a,b)$$$ that satisfy the following conditions:

1. $$$0\le b\le a \lt p^k$$$;
2. $$$\binom{a}{b} \equiv x \pmod p$$$.

You are given an integer $$$n$$$. For each $$$p\leq q$$$, where $$$pq \mid n$$$, denote $$$r=\frac pq$$$. Find the number of different values of $$$r$$$.

$$$2^n$$$ contestants take part in a programming contest. They are labeled from $$$1$$$ to $$$2^n$$$, and the contestant labeled $$$i$$$ has a level of $$$a_i$$$. It is guaranteed that $$$a_1, a_2, \ldots, a_{2^n}$$$ forms a permutation of length $$$2^n$$$ (i.e., each $$$a_i$$$ is an integer in the range $$$[1,2^n]$$$, and $$$a_1,a_2,\ldots,a_{2^n}$$$ are pairwise distinct).

The contest takes the form of an elimination series. There are $$$n$$$ rounds; each round will knock out exactly half of the contestants. In each round, let $$$m$$$ be the current number of contestants, then the contestant with the smallest label (i.e., the label of each contestant remains unchanged throughout the contest) competes with the contestant with the second smallest label, the contestant with the third smallest label competes with the contestant with the fourth smallest label, and so on. In each competition, the contestant with a lower level is eliminated, while the contestant with a higher level will advance to the next round.

Little D is the contestant labeled $$$x$$$. He wants to use magic before the contest to win as many competitions as possible. Specifically, he can perform the following operation no more than $$$k$$$ times: choose two contestants other than himself and swap their levels. Note that the operation can only be done before the contest.

For each $$$x=1,2,\ldots,2^n$$$, print the maximum number of competitions he can win.

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

We define the value of an interval $$$[l,r]$$$ as $$$$$$\max_{\substack{l\le i \lt j \lt k\le r\\j-i\le k-j}}\gcd(a_i,a_j,a_k).$$$$$$ If $$$r-l\le 1$$$, the value is $$$0$$$.

There will be $$$q$$$ queries. In each query, you need to find the value of a particular interval.

There are $$$10^9+1$$$ graphs with $$$n$$$ vertices each. In the $$$0$$$-th graph $$$G_0(V_0,E_0)$$$, there is an edge between vertices $$$i$$$ and $$$i+1$$$ for all $$$1\leq i \lt n$$$.

Denote the length of the shortest path between $$$x$$$ and $$$y$$$ in the graph $$$i$$$ by $$$d_{i}(x,y)$$$. If $$$x$$$ and $$$y$$$ aren't reachable from each other, let $$$d_i(x,y)$$$ be $$$-1$$$. In the graph $$$i$$$ ($$$i\geq 1$$$), there's an edge between $$$x$$$ and $$$y$$$ if and only if $$$d_{i-1}(x,y)\geq k$$$.

There are $$$q$$$ queries. In each query you are given five numbers $$$t,n,k,x,y$$$. You need to output $$$d_{t}(x,y)$$$.

There are $$$n$$$ penguins, where the width of the $$$i$$$-th penguin is $$$w_i$$$. They enter the refrigerator in an order specified by the permutation $$$p_i$$$: the $$$p_i$$$-th penguin enters the refrigerator at position $$$i$$$.

The refrigerator has a width of $$$W$$$, and its depth is considered infinite. After all these penguins have entered the refrigerator, they can swap positions if the sum of the widths of adjacent penguins does not exceed $$$W$$$. A penguin can swap positions multiple times.

Calculate how many different exit orders are possible from the refrigerator, as well as the lexicographically smallest order among all possible ways for the penguins to exit the refrigerator.

The refrigerator has only one door and operates as a "last in, first out" (LIFO) structure, which means the penguins will exit in the reverse order of their entry.

Little D wants to build a prism palace using two parallel planes $$$A(z=0)$$$ and $$$B(z=10^9)$$$ that she has. To finish her build, she borrows a convex polygon $$$P$$$ consisting of $$$n$$$ points from Little N. She puts two identical copies of $$$P$$$ on the two planes, one on each. The two polygons must be identical to $$$P$$$ and must be able to coincide by translating the polygon on $$$A$$$ along some vector $$$(d_x, d_y, 10^9)$$$ to the polygon on $$$B$$$ without rotating.

Together, the two polygons form a prism-shaped palace between them. Let the projection area of the prism's sides perpendicularly onto plane $$$A$$$ be $$$S_1,S_2,\cdots S_n$$$, and the probability of the multiset $$$\{S_i\}$$$ being cool be $$$f(r)$$$, assuming that $$$(d_x, d_y)$$$ is chosen uniformly at random from the circle centered at $$$(0,0)$$$ with a radius $$$r$$$, i.e., $$$d_x^2 + d_y^2 \le r^2$$$. Here, a multiset of real numbers $$$S$$$ is cool if there exists an element $$$x$$$ in $$$S$$$ such that $$$\sum\limits_{y\in S}y=2x$$$. It can be proved that the limit $$$\lim_{r \rightarrow \infty} f(r)$$$ does exist, and you need to find this limit.

There are $$$n$$$ random variables. Each of them is chosen uniformly at random from $$$[1, m] \cap \mathbb{Z}$$$.

Let $$$occ_i$$$, where $$$i\in [1,m] \cap \mathbb{Z}$$$, denote the number of times the value $$$i$$$ occurs among the $$$n$$$ variables. Let $$$M=\max \{occ_i|i\in [1,m] \cap\mathbb{Z}\}$$$ .

For example, if $$$n=5,m=5$$$, the variables can be $$$\{4,4,3,1,5\}$$$ with probability $$$\frac{1}{3125}$$$. We have $$$occ_1=1$$$, $$$occ_2=0$$$, $$$occ_3=1$$$, $$$occ_4=2$$$, $$$occ_5=1$$$, $$$M=\max\{1,0,1,2,1\}=2$$$.

Now you're given $$$n$$$ and $$$m$$$; please work out the expected value of $$$M$$$. For convenience, let's denote the answer as $$$\mathrm E(M)$$$, then you only need to output $$$\mathrm E(M)\times m^n$$$ modulo $$$p$$$.