The first major village, Zhangjia Village, has reached its once-in-a-decade election for village chief.

This year, there are two candidates for village chief: Wang Xiaochang and Liu Xiaopeng.

Each villager has their own preference level for the two candidates, represented by an integer $$$a$$$. Specifically:

• $$$a \gt 0$$$ means the villager will vote for Xiaochang.
• $$$a \lt 0$$$ means the villager will vote for Xiaopeng.
• $$$a = 0$$$ means the villager may vote for either candidate.

To secure the election, both candidates can use their "money power" to sway votes. This ability can be used infinitely, and each use costs 1 yuan to increase or decrease someone's preference level by 1.

Xiao Ming, as an observer, happily recorded the highlights of the election in the $$$Q$$$ minutes leading up to it.

Specifically, from $$$Q$$$ minutes before the election to 1 minute before the election, one of the following three events occurred every minute:

1. '1 x y': A group of $$$x$$$ villagers with a preference level of $$$y$$$ arrives at the polling station.
2. '2 k': Wang Xiaochang repeatedly uses his money power on the villager whose preference level is closest to 0 and not currently voting for him until at least $$$k$$$ villagers are confirmed to vote for him. If at the start of the minute, there are already at least $$$k$$$ villagers voting for him, nothing is done.
3. '3 k': Liu Xiaopeng repeatedly uses his money power on the villager whose preference level is closest to 0 and not currently voting for him until at least $$$k$$$ villagers are confirmed to vote for him. If at the start of the minute, there are already at least $$$k$$$ villagers voting for him, nothing is done.

Now, Xiao Ming has returned home and is organizing his records. Please help Xiao Ming calculate how much money each candidate spent in each minute for records of type '2' or '3'.

Tomorrow is Xiao Peng's birthday, so Xiao Chang wants to give some gifts to Xiao Peng.

Xiao Chang buys $$$n$$$ gifts from the Internet and arranges them in a row from left to right. Each gift has a positive integer eigenvalue, where the $$$i$$$th gift from left to right has eigenvalue $$$a_i$$$. Since it is a bit scary to give all these gifts in one go, he decides to choose an interval in which to give these gifts to his little friend.

However, Xiao Chang, who is extremely sensitive to duplicates, acutely realizes that there are intervals $$$[l,r]$$$ that are with duplicates! Specifically, if Xiao Chang can select at least two distinct non-empty subsequences (not necessarily consecutive) from the interval $$$[l,r]$$$ such that the Least Common Multiple of every number in these two subsequences is equal to the Least Common Multiple of every number in the interval $$$[l,r]$$$. Formally, for the subscripted full set $$$U = [l,r] \cap \mathbb{Z}$$$, if two non-empty sets $$$S,T$$$ can be found that satisfy $$$S \ne T$$$, $$$S \subseteq U$$$, $$$T \subseteq U$$$, $$$\operatorname{lcm}_{x \in S} a_x = \operatorname{lcm}_{x \in T} a_x = \operatorname{lcm}_{x \in U} a_x$$$, then the interval $$$[l,r]$$$ is said to be with duplicates.

Since it's one day before Xiao Peng's birthday, now, a bored Xiao Chang wants to know how many intervals $$$[l,r]$$$ are with duplicates.

Electrician Master Xiao Ming is repairing an electrical box.

There are $$$n$$$ components arranged in a row in the electrical box, numbered from left to right as $$$1,2,3,\ldots,n$$$. There are also $$$m$$$ wires connecting pairs of components. The $$$i$$$-th wire ($$$1 \le i \le m$$$) connects components numbered $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \lt y_i \le n$$$), and any two components are directly connected by at most one wire, i.e., $$$\forall 1 \le i \lt j \le m$$$, $$$x_i \ne x_j$$$ or $$$y_i \ne y_j$$$. Current can flow through the wires in any direction. We refer to a wire connecting components $$$a$$$ and $$$b$$$ as an unordered pair $$$(a,b)$$$, meaning $$$(a,b)$$$ and $$$(b,a)$$$ represent the same wire.

To facilitate maintenance, the electrical box must satisfy the requirement:

no two wires intersect, i.e., $$$\forall 1 \le i \lt j \lt k \lt l \le n$$$, wires $$$(i,k)$$$ and $$$(j,l)$$$ cannot coexist.

Xiao Ming has a detection tool with four probes. When these probes are connected to four distinct components $$$i,j,k,l$$$ in sequence, if the wires $$$(i,j)$$$, $$$(j,k)$$$, and $$$(k,l)$$$ all exist, the tool can detect whether this circuit segment is functioning properly.

Xiao Ming is in a hurry to leave work, so he wants to know how many such circuit segments need to be tested. Specifically, he needs to count the number of ordered quadruples $$$(i,j,k,l)$$$ satisfying:

1. $$$i,j,k,l$$$ are pairwise distinct.
2. Wires $$$(i,j)$$$, $$$(j,k)$$$, and $$$(k,l)$$$ all exist.

During the repair process, Xiao Ming will sequentially add $$$q$$$ wires. The $$$i$$$-th wire ($$$1 \le i \le q$$$) connects components $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i \lt v_i \le n$$$). As a qualified electrician, after adding each wire, the electrical box must still satisfy all the aforementioned requirements. After each addition, Xiao Ming must perform a full inspection. Therefore, he needs to determine the number of valid ordered quadruples in the initial electrical box and after each wire addition.

Xiaopeng is a warehouse keeper. One day, he was idle and decided to arrange the boxes he manages.

There are now $$$n$$$ closely adjacent shelves, where the height of the $$$i$$$-th shelf from left to right is $$$a_i$$$. Specifically, $$$a_0 = a_{n+1} = +\infty$$$. There are $$$m$$$ boxes of size 1 to be placed on these shelves. Xiaopeng considers a placement scheme "good" if it satisfies the following conditions:

We model the warehouse as a two-dimensional Cartesian coordinate system. If a box is placed at coordinate $$$(x,y)$$$, then:

• $$$a_x \lt y$$$.
• $$$(x,y-1)$$$ either satisfies $$$a_x \ge y-1$$$ or has a box placed at $$$(x,y-1)$$$.
• $$$(x-1,y)$$$ either satisfies $$$a_{x-1} \ge y$$$ or has a box placed at $$$(x-1,y)$$$.
• $$$(x+1,y)$$$ either satisfies $$$a_{x+1} \ge y$$$ or has a box placed at $$$(x+1,y)$$$.

Xiaopeng wants to determine the total number of good placement schemes. The answer should be taken modulo $$$10^9+7$$$.

Xiao Chang and Xiao Peng want to play a game.

The game is played on a directed acyclic graph (DAG) with $$$2^n$$$ nodes (labeled $$$0$$$ to $$$2^n-1$$$) and $$$m$$$ edges. There are $$$k$$$ pieces placed on the graph, with the $$$i$$$-th piece initially located at node $$$a_i$$$. The two players take turns, with Xiao Chang moving first. On each turn, a player can freely choose any piece and move it one step along any outgoing edge from its current node. If a player cannot make any move on their turn (i.e., all pieces are on nodes with no outgoing edges), that player loses the game. Note: Multiple pieces can occupy the same node.

Naturally, Xiao Chang and Xiao Peng are perfectly rational: once the initial positions of the pieces are set, they both already know who will win or lose the game. So, they decide to manipulate the initial positions $$$a_i$$$! They observe that each $$$a_i$$$ can be uniquely represented as an $$$n$$$-bit binary number. If they write down the binary representations of all $$$k$$$ pieces row by row, they will form a $$$k \times n$$$ binary matrix, where the value at the $$$i$$$-th row and $$$j$$$-th column indicates whether the $$$j$$$-th bit (from least to most significant, with the least significant bit being the 1st bit) of $$$a_i$$$ is 0 or 1.

They assign a position number $$$(i-1) \times n+j$$$ to each cell $$$(i,j)$$$ in the matrix. Starting from position 1, they take turns deciding whether each cell should be 0 or 1, with Xiao Chang going first, followed by Xiao Peng, until the entire matrix is filled (i.e., Xiao Chang decides the first position, Xiao Peng the second, Xiao Chang the third, and so on). In this way, they "scheme against each other" to determine all $$$a_i$$$.

Afterward, Xiao Chang makes the first move in the DAG-based game described earlier. However, the game is still too simple for them, so they want to ask you: Under these rules, who will be the ultimate winner?

Some unexpected incidents occurred during the village chief election. Due to Xiaochang and Xiaopeng violating election rules and being disqualified, Xiao Ming was ultimately elected as the new village chief. As a result, Xiao Ming decided to treat everyone to a meal together.

In Zhangjia Village, the local customs are quite bold; meals must involve drinking wine and playing a game called "Drink to the Finish".

To describe this game specifically: $$$n$$$ people sit in a circle, and the $$$i$$$-th person holds a die that can roll an integer between $$$[1,a_i]$$$ with equal probability.

The game proceeds in rounds. At the start of each round:

(1) All people who have not yet become "wine dazed" roll their dice once.

(2) Now, each person checks the numbers rolled by their left and right neighbors. Assuming their own rolled number is $$$x$$$, and their left and right neighbors' numbers are $$$a$$$ and $$$b$$$ respectively, then in this round they need to drink $$$\max(0,a-x)+\max(0,b-x)$$$ grams of wine.

(3) Those who roll $$$x=1$$$ in this round will become "wine dazed" and can no longer roll their dice. Their number is fixed at 1 thereafter.

(4) The game ends when everyone has become "wine dazed".

Xiao Ming is worried that everyone might drink too much, but also wants to know whether his wine tolerance can last until the game ends. So he asks you to calculate: In this game, how many grams of wine is each person expected to drink?

Xiaochang and Xiaopeng are preparing for the postgraduate entrance exam together, sitting back-to-back in the study room day after day.

Originally, Xiaochang was better at studying than Xiaopeng, so he doesn't want Xiaopeng to surpass him. Xiaopeng is very hardworking himself, but he doesn't want Xiaochang to see him working too hard.

Specifically:

• Xiaochang has a sequence $$$A$$$ of length $$$n$$$, where the $$$i$$$-th position ($$$0 \le i \lt n$$$) $$$A_i$$$ is either 1 or 0, representing whether he looks back to check if Xiaopeng is working hard (1) or not (0).
• Xiaopeng has a sequence $$$B$$$ of length $$$m$$$, where the $$$j$$$-th position ($$$0 \le j \lt m$$$) $$$B_j$$$ is either 1 or 0, representing whether he is working hard (1) or playing with his phone (0) at that moment.

Over the next $$$n \times m$$$ days, at 11:00 am on the $$$k$$$-th day ($$$0 \le k \lt n \times m$$$):

• If $$$A_{k \bmod n}=1$$$, Xiaochang will look back at Xiaopeng; otherwise, he won't.
• If $$$B_{k \bmod m}=1$$$, Xiaopeng will be working hard at that moment; otherwise, he will be playing with his phone.

The trust level of Xiaochang towards Xiaopeng increases by 1 in the following two cases:

1. Xiaochang looks back and sees Xiaopeng playing.
2. Xiaochang doesn't look back, but Xiaopeng is working hard.

Given $$$n$$$, $$$m$$$, and Xiaochang's sequences, the question is: Assuming Xiaopeng constructs his sequence in the optimal way, what is the maximum trust level Xiaochang can have towards Xiaopeng after $$$n \times m$$$ days?

Xiao Ming has a string $$$S$$$ of length $$$N$$$, where each character belongs to the set $$$\Sigma=\{a,b,c,d,e\}$$$.

The hash value of a string $$$T$$$ of length $$$M$$$ is defined as $$$\sum_{i=1}^{M}(T_i-\text{'a'}+1) \times 1331^{M-i} \pmod{2^{32}}$$$. Here, the subtraction is performed by converting the characters to their corresponding ASCII codes.

Now, Xiao Ming has $$$Q$$$ queries. Each query consists of three positive integers $$$l,r,k$$$. You need to consider all distinct subsequences within the interval $$$[l,r]$$$ that start with the character $$$S_l$$$, end with the character $$$S_r$$$, and have a length of at least 2. These subsequences should be sorted lexicographically from smallest to largest, and you should output the hash value of the $$$k$$$-th subsequence in this order. Specifically, if the number of distinct subsequences in the interval $$$[l,r]$$$ is less than $$$k$$$, output '-1'.

A subsequence within the interval $$$[l,r]$$$ is obtained by deleting some characters from that interval. Two subsequences with lengths $$$a$$$ and $$$b$$$, respectively, are considered distinct if and only if $$$a \ne b$$$, or there exists an integer $$$i$$$ such that $$$1 \le i \le a$$$ and the $$$i$$$-th characters of the two subsequences differ.

Xiao Ming is obsessed with a strange game that takes place on a 2D coordinate plane. He controls a small airplane starting at the origin point $$$(0,0)$$$.

As a top pilot, he receives a flight command sequence, which is a permutation $$$P$$$ of the four letters 'NEWS'.

Xiao Ming will perform $$$n$$$ flights in total. For his $$$i$$$-th flight:

If $$$1 \le i \le 4$$$, the flight command is the $$$i$$$-th letter in $$$P$$$.

If $$$i \gt 4$$$, the flight command is the same as the $$$(i-4)$$$-th flight.

The meaning of each command is as follows:

'N': If the current position is $$$(x,y)$$$, move to $$$(x,y+1)$$$. Repeat this until reaching a new unvisited point.

'E': If the current position is $$$(x,y)$$$, move to $$$(x+1,y)$$$. Repeat this until reaching a new unvisited point.

'W': If the current position is $$$(x,y)$$$, move to $$$(x-1,y)$$$. Repeat this until reaching a new unvisited point.

'S': If the current position is $$$(x,y)$$$, move to $$$(x,y-1)$$$. Repeat this until reaching a new unvisited point.

After completing all $$$n$$$ flights, calculate the sum of the two coordinates of his final position.

There are $$$n$$$ children sitting in a circle playing a message-passing game. The children are numbered from $$$0$$$ to $$$n-1$$$, and each of them is facing the center of the circle.

Each child holds a card. The card of the $$$i$$$-th child has a number $$$a_i$$$ on it, where $$$a_i \in \{2,3\}$$$.

If the $$$i$$$-th child receives the message, they will pass it to child number $$$(i+a_i) \bmod n$$$.

The teacher wants to inform one child such that eventually every child receives the message. Your task is to help the teacher rearrange the positions of the children and choose one child to initially receive the message. Determine whether it is possible to make sure that all children will receive the message.

Xiao Ming is a little girl who likes eating cucumbers.

She enjoys playing chess against herself, acting as both the black and white sides simultaneously.

The game is played on an undirected graph $$$G$$$ with $$$n$$$ nodes, containing $$$m$$$ undirected edges. The $$$i$$$-th edge connects nodes $$$u_i$$$ and $$$v_i$$$ with a length of $$$l_i$$$. It is guaranteed that the graph contains no self-loops but may have multiple edges between the same pair of nodes.

In each move, Xiao Ming can choose either side and place a chess piece of the corresponding color on any unoccupied node. After $$$n$$$ rounds, the game ends.

Black and white represent yin and yang, and Xiao Ming wishes to maintain their balance. Therefore, she wants to ensure that no two chess pieces of the same color are placed too close to each other on the graph. Specifically, we consider a simple path $$$p_1,p_2\ldots p_k$$$ that satisfies:

1. $$$k \ge 2$$$
2. $$$p_1,p_2\ldots p_k$$$ are all distinct.
3. Nodes $$$p_1$$$ and $$$p_k$$$ are occupied by chess pieces of the same color.

Xiao Ming defines the balance degree $$$d$$$ of the game as the minimum path length among all such paths that meet the above conditions. If no such path exists, the balance degree is defined as positive infinity.

Please help Xiao Ming plan the game to maximize the balance degree $$$d$$$.

Xiao Ming is going hiking and needs to pack some clothes.

He has $$$n$$$ clothes, and the $$$i$$$-th one keeps him warm by $$$a_i$$$ points. He can choose to bring $$$1 \sim n$$$ clothes to meet the weather for the next $$$m$$$ days.

Each day has different rules:

If $$$t_i=1$$$, the total warmth of the clothes he wears that day must be at least $$$x_i$$$.

If $$$t_i=2$$$, the total warmth must not exceed $$$x_i$$$.

Each day, he can pick some of the clothes he packed (but must wear, so at least one).

What's the smallest number of clothes he needs to bring to meet all days' rules? If it's impossible, output $$$-1$$$.

Xiao Chang and Xiao Ming live in a tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. There are a number of kingdoms in the tree.

If a node has more than two edges, then a kingdom appears at that node with the same number as the node (at least one such node is guaranteed to exist). The capital of the kingdom is this node. The kingdom expands its territory as much as possible on a "first come, first served" basis. In other words, an unoccupied node will be occupied by the kingdom whose capital is the closest to the node (if there is more than one, the one with the smallest number).

Xiao Chang and Xiao Ming are friends, so Xiao Chang will often visit Xiao Ming, and on the way, he may pass the territories of several kingdoms. Also, to save time, Xiao Chang will follow the shortest path to reach Xiao Ming's home. Now you need to answer $$$q$$$ queries, given $$$u$$$ and $$$v$$$, assuming that Xiao Chang lives in $$$u$$$ and Xiao Ming lives in $$$v$$$, how many kingdoms will Xiao Chang visit on his way to visit Xiao Ming?