Little G is an intelligent being living on planet $$$\mathbf{H}$$$. On this planet, there are endless fields of flowers, and Little G loves hopping among them. On the $$$(10^9+7)$$$-th day of playing in the flower fields, Little G learned about Manhattan distance and immediately invented a game with it.

Little G's game works as follows: choose a square patch of flowers and divide it into $$$n^2$$$ identical smaller squares arranged in $$$n$$$ rows and $$$n$$$ columns, then hop between all the vertices of these squares. Each hop must cover a Manhattan distance of exactly a given positive integer $$$K$$$. Moreover, Little G does not want to get lost, so he wants to eventually return to the starting point after a sequence of hops.

Little G quickly found a simple solution: start at a corner vertex, hop to a vertex at Manhattan distance $$$K$$$, and hop back. This immediately gives all solutions with an even number of hops. But Little G thinks this is too easy — he wants to find solutions with an odd number of hops, and asks for your help.

Based on his experience, Little G believes that finding the minimum number of hops is sufficient to construct solutions with more hops. So you only need to report the minimum number of hops among all solutions with an odd number of hops, or report that no such solution exists. Since Little G has not yet decided on $$$n$$$ or $$$K$$$, he will ask you $$$T$$$ queries, each specifying positive integers $$$n$$$ and $$$K$$$.

To help you (a human) better understand the mysterious ideas of planet $$$\mathbf{H}$$$'s inhabitants: consider all vertices of the divided squares as lattice points in the Cartesian plane with both coordinates being integers in $$$[0, n]$$$. We call these special points. A hop between two special points $$$\mathbf{I}(x_1,y_1)$$$ and $$$\mathbf{T}(x_2,y_2)$$$ is valid if and only if $$$|x_1-x_2|+|y_1-y_2|=K$$$.

For each query with given positive integers $$$n$$$ and $$$K$$$: determine whether there exists a cycle starting and ending at some special point, following the hopping rules, with an odd number of hops. If such a cycle exists, output the minimum number of hops; otherwise, output $$$-1$$$.

In Japanese, the digits $$$1$$$ through $$$9$$$ are pronounced as follows:

To read a multi-digit number, simply concatenate the Japanese readings of each digit from left to right. For example, $$$15$$$ is read as ichigo, and $$$893$$$ is read as hachikyuusan.

What is $$$72$$$ in Japanese?

Given a positive integer $$$N$$$, define the repunit $$$R(k)$$$ as the number consisting of $$$k$$$ ones, i.e., $$$R(k) = \underbrace{11\ldots1}_{k}$$$.

Find the largest positive integer $$$k$$$ such that $$$R(k)$$$ is a divisor of $$$N$$$, and output $$$k$$$.

Note that $$$R(1) = 1$$$ divides every positive integer, so the answer is at least $$$1$$$.

This is an interactive problem.

There is a hidden partition of the integers $$$1, 2, \ldots, n$$$ into $$$\frac{n}{k}$$$ disjoint $$$k$$$-tuples. It is guaranteed that $$$k \mid n$$$.

You need to determine all hidden $$$k$$$-tuples through queries.

In each query, you may choose a set $$$S \subseteq \{1, 2, \ldots, n\}$$$, and the interactor will return an integer indicating how many hidden $$$k$$$-tuples are entirely contained in $$$S$$$.

The number of queries must not exceed $$$n\lceil \log_2 n \rceil$$$.

$$$tarjen$$$ has recently been playing Roco Kingdom and wants to catch some shiny spirits.

To farm shiny spirits, $$$tarjen$$$ must first repeatedly catch regular spirits. Catching regular spirits accumulates the pollution progress of a shiny pool. When the pollution progress reaches the required threshold, a corrupted spirit belonging to that pool spawns on the map. After defeating a corrupted spirit, there is a chance to encounter a shiny spirit.

However, the number of corrupted spirits on the map is limited. If too many spawn, old corrupted spirits are pushed out by new ones.

Additionally, there is a pity mechanism for shiny encounters. Each shiny pool has an independent pity counter. Each time a corrupted spirit from that pool is defeated, the pool's pity counter increases by one. When a pool's pity counter reaches $$$80$$$, defeating a corrupted spirit from that pool is guaranteed to trigger a shiny encounter.

The detailed rules are as follows.

There are $$$n$$$ types of regular spirits, $$$A$$$ families, and $$$B$$$ elements. The $$$i$$$-th type of regular spirit belongs to family $$$fa_i$$$ and has element $$$el_i$$$.

There are two types of shiny pools:

• Family pool $$$F_x$$$: the shiny pool for the $$$x$$$-th family.
• Element pool $$$E_x$$$: the shiny pool for the $$$x$$$-th element.

Each shiny pool $$$P$$$ maintains four values:

• $$$progress_P$$$: pollution progress, initially $$$0$$$.
• $$$pity_P$$$: pity counter, initially $$$0$$$.
• $$$need_P$$$: the number of regular catches needed to spawn one corrupted spirit (a given constant).
• $$$luck_P$$$: the luck threshold (a given constant).

At most $$$m$$$ corrupted spirits can exist on the map simultaneously. All corrupted spirits are arranged in a queue ordered by spawn time (oldest first). If the count exceeds $$$m$$$, the oldest corrupted spirits are removed from the front until the count is at most $$$m$$$. Corrupted spirits pushed out by the map capacity are not considered defeated and do not affect any pool's pity counter.

There are $$$q$$$ operations, each being one of the following two types.

Operation 1: Regular Catch

C T x c

$$$tarjen$$$ catches the $$$x$$$-th type of regular spirit $$$c$$$ times consecutively, crediting these $$$c$$$ catches to a certain shiny pool. If $$$T = F$$$, credit to family pool $$$F_{fa_x}$$$; if $$$T = E$$$, credit to element pool $$$E_{el_x}$$$.

Let the credited pool be $$$P$$$. Set $$$progress_P \mathrel{+}= c$$$. Then, whenever $$$progress_P \ge need_P$$$, spawn one corrupted spirit belonging to pool $$$P$$$ and set $$$progress_P \mathrel{-}= need_P$$$.

Note that a single catch operation may spawn multiple corrupted spirits.

The newly spawned corrupted spirits are appended to the end of the queue in order. If the count exceeds $$$m$$$, the oldest corrupted spirits are removed from the front.

Operation 2: Defeat Corrupted Spirit

B k r

$$$tarjen$$$ challenges the $$$k$$$-th corrupted spirit on the map (ordered from oldest to newest).

If there are fewer than $$$k$$$ corrupted spirits on the map, output MISS and no state changes occur.

Otherwise, let the corrupted spirit belong to pool $$$P$$$. Remove it from the map and set $$$pity_P \mathrel{+}= 1$$$.

Then perform the shiny check. Each pool $$$P$$$ has a luck threshold $$$luck_P$$$. If $$$r \le luck_P$$$ or $$$pity_P = 80$$$, a shiny is encountered: output SHINY P and set $$$pity_P = 0$$$. Otherwise, output NORMAL P $$$pity_P$$$.

Given an integer $$$K$$$ and two arrays $$$a_{1\sim 2^{K}-1}$$$ and $$$b_{1\sim 2^{K}-1}$$$, each of size $$$2^{K}-1$$$.

There is an undirected complete graph $$$G$$$ of size $$$2^K$$$ with vertices numbered $$$0\sim 2^K - 1$$$.

For a spanning tree $$$T$$$ of $$$G$$$, define $$$A(T)=\prod_{(u,v)\in T}a_{u\oplus v}$$$, $$$B(T)=\sum_{(u,v)\in T}b_{u\oplus v}$$$, $$$C(T)=\oplus_{(u,v)\in T}(u\oplus v)$$$.

For each $$$0\le x \lt 2^K$$$, compute $$$(\sum_{T,C(T)=x}A(T)B(T)^p) \bmod 998244353$$$, where $$$p$$$ is a given constant.

We define $$$0^0=1$$$.

Given an integer sequence $$$a$$$ of length $$$n$$$ with values in $$$[0,2]$$$.

An operation is defined as choosing an index $$$x\in [1,n-2]$$$:

- Let $$$s=(a_x+a_{x+1}+a_{x+2})\bmod 3$$$, then set $$$a_x,a_{x+1},a_{x+2}$$$ all to $$$s$$$ simultaneously.

You need to perform some operations (possibly none) to maximize the sum of all elements in sequence $$$a$$$. Additionally, you must provide a valid operation sequence whose length does not exceed $$$\lfloor\dfrac{5}{7}n\rfloor+100$$$.

Given a simple undirected connected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges, you need to choose two distinct edges to delete, obtaining a new graph $$$G'$$$, such that $$$G'$$$ remains connected.

Let the two deleted edges be $$$(p,q)$$$ and $$$(u,v)$$$. You need to minimize the sum of the shortest path between $$$p$$$ and $$$q$$$ in $$$G'$$$ plus the shortest path between $$$u$$$ and $$$v$$$ in $$$G'$$$. Output this minimum value and the number of deletion schemes that achieve it.

Koishi found a positive integer sequence $$$a = [a_1, a_2, \cdots, a_n]$$$ of length $$$n$$$ on the road, satisfying $$$1\le a_i\le n$$$. She then computed the prefix maximum sequence $$$b = [b_1, b_2, \cdots, b_n]$$$, where $$$b_i$$$ is the maximum of the first $$$i$$$ elements of $$$a$$$:

$$$$$$b_i = \max\{a_1, a_2, \cdots, a_i\} = \max_{1\le j\le i}\{a_j\}$$$$$$

After obtaining both sequences, Koishi merged them together, defining a sequence $$$c$$$ of length $$$2n$$$ as $$$c = [a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_n]$$$, and sorted $$$c$$$ in non-decreasing order.

Being the girl of the unconscious, Koishi lost the values of $$$a$$$ and $$$b$$$, and only the sequence $$$c$$$ remains.

Being the girl of the unconscious, Koishi has given the sequence $$$c$$$ to you — the cutest college student of the 21st century — hoping that you can find any valid sequence $$$a$$$. There may be multiple valid sequences; you only need to output any one of them. There may also be no valid sequence, in which case you should report that no solution exists.

$$$tarjen$$$ has a permutation $$$p$$$ of length $$$n$$$. You may perform at most one operation: choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) and reverse the subarray $$$p_l, p_{l+1}, \ldots, p_r$$$.

What is the maximum number of inversions in the permutation after the operation?

An inversion is a pair of indices $$$(i, j)$$$ satisfying $$$1 \le i \lt j \le n$$$ and $$$p_i \gt p_j$$$.

$$$tarjen$$$ is playing a game of combining two trees into one graph.

He took two trees on $$$n$$$ vertices and combined them into an undirected unweighted graph $$$G = (V, E)$$$ with $$$n$$$ vertices and $$$m = 2n - 2$$$ edges.

But now he cannot decompose the graph back into two trees — please help him!

Formally, partition all edges into exactly two sets $$$T$$$ and $$$E \setminus T$$$ such that both $$$T$$$ and $$$E \setminus T$$$ form spanning trees of $$$G$$$.

You may output any valid partition. It is guaranteed that a valid partition exists.

The graph may contain parallel edges but no self-loops.

Dou Di Zhu (Fight the Landlord) is one of the most popular card games in China. The game uses a standard 54-card deck (52 regular cards + 2 jokers).

In Dou Di Zhu, a straight is a hand of at least 5 cards with consecutive ranks. The ranks in ascending order are: 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A. Note that 2 and the jokers cannot appear in a straight.

$$$tarjen$$$ currently holds 17 cards and loves straights. He wants to know the length of the longest straight he can play. Can you help him?

If no straight can be played, output 0.

$$$tarjen$$$ is the guardian of the Crystal Castle. The castle's corridor is inlaid with a row of $$$n$$$ magic crystals, where the $$$i$$$-th crystal has color number $$$a_i$$$. Adjacent crystals of the same color resonate and form a color segment — a maximal run of consecutive identical colors. For example, the color sequence $$$[1, 1, 2, 2, 1]$$$ has $$$3$$$ color segments: $$$[1, 1]$$$, $$$[2, 2]$$$, and $$$[1]$$$.

Every day, travelers come and ask $$$q$$$ questions. Each question specifies an interval $$$[l, r]$$$: if we take out these crystals, randomly shuffle them (choosing uniformly at random among all permutations with repetition), what is the expected number of color segments?

Output the answer modulo $$$998244353$$$. That is, if the answer is an irreducible fraction $$$\frac{p}{q}$$$, output $$$p \cdot q^{-1} \bmod 998244353$$$. It can be shown that $$$q^{-1} \bmod 998244353$$$ always exists under the constraints of this problem.