Prof. Pang has a rooted tree which is rooted at $$$1$$$ with $$$n$$$ nodes. These $$$n$$$ nodes are numbered from $$$1$$$ to $$$n$$$.

Now he wants to start the depth-first search at the root. He wonders for each node $$$v$$$, what is the minimum and the maximum position it can appear in the depth-first search order. The depth-first search order is the order of nodes visited during the depth-first search. A node appears in the $$$j$$$-th ($$$1\le j\le n$$$) position in this order means it is visited after $$$j-1$$$ other nodes. Because sons of a node can be iterated in arbitrary order, multiple possible depth-first orders exist. Prof. Pang wants to know for each node $$$v$$$, what are the minimum value and the maximum value of $$$j$$$ such that $$$v$$$ appears in the $$$j$$$-th position.

Following is a pseudo-code for the depth-first search on a rooted tree. After its execution, dfs_order is the depth-first search order.

let dfs_order be an empty list

def dfs(vertex x):
    append x to the end of dfs_order.
    for (each son y of x): // sons can be iterated in arbitrary order.
        dfs(y)

dfs(root)

Prof. Pang recently got a dictionary of the elvish language, including many strings representing their words. He thinks a partition of string $$$s$$$ is beautiful if both of the following conditions are satisfied:

• $$$s = s_1 + s_2 + s_3 + s_4 + s_5 + s_6$$$, where $$$s_i (1\leq i\leq 6)$$$ are nonempty substrings. $$$a + b$$$ means the concatenation of string $$$a$$$ and $$$b$$$ here.
• $$$s_1 = s_2 = s_5, s_3 = s_6$$$.

For example, you can partition the string "114514" into $$$6$$$ parts : "114514" = "1" + "1" + "4" + "5" + "1" + "4". The first, second, fifth parts are the same, and the third and sixth parts are the same. Thus, the partition of $$$s=$$$"114514" into $$$s_1=$$$"1", $$$s_2=$$$"1", $$$s_3=$$$"4", $$$s_4=$$$"5", $$$s_5=$$$"1", and $$$s_6=$$$"4" is beautiful.

Accordingly, the beauty of a string $$$s$$$ is defined as the number of beautiful partitions of $$$s$$$.

Given a string $$$t$$$, please help Prof. Pang to figure out the sum of beauties of all substrings of $$$t$$$.

While most people love to play Wordle these days, Prof. Pang has become addicted to String-dle.

String-dle is an interesting string-guessing game where the player tries to guess a string of $$$k$$$ capital letters through several rounds. In each round, the player submits a string of length $$$k$$$ as his guess, and the system grades the guess through the following pseudo-code:

def grading(answer, guess):
  let count be a hash map
  for i = 1 to k:
    if answer[i] not in count:
      count[answer[i]] = 1
    else:
      count[answer[i]] = count[answer[i]] + 1
  let grade be an array of length k
  for i = 1 to k:
    if answer[i] == guess[i]:
      grade[i] = 'O'
      count[guess[i]] = count[guess[i]] - 1
  for i = 1 to k:
    if answer[i] != guess[i]:
      if count[guess[i]] > 0:
        grade[i] = '-'
        count[guess[i]] = count[guess[i]] - 1
      else:
        grade[i] = 'x'
  return grade

The grade consisting of O (capital letter O), - (dash), and x (small letter x) is then returned to the player, and the player may base his next guess on the previous grades. The following is an example of one game Prof. Pang played:

G: CRANE
A: xx–x
G: UTTER
A: xxOxx
G: NASAL
A: OOxOO
G: NATAL
A: OOOOO

Strings after G are Prof. Pang's guesses and strings after A are the grades of the guesses.

Prof. Pang really enjoys the game. He believes that he has developed a perfect strategy for it. However, today he goes mad because he thinks the grading system is bugged! He wants to have someone write an analysis program to figure out the number of possible strings that can be the answer to the puzzle based on his list of guesses and grades.

Since the grading system might be bugged, it might not conform to the pseudo-code given above. So specifically, the task is to find how many strings that are consistent with the input. A string s is consistent with the input if for any guess g in the input and its corresponding grade d, grading(s, g)=d.

And of course, you will be doing the programming.

Prof. Pang has bought a humanoid cleaning robot to clean his yard. The robot is not very sophisticated. It can either move forward or change its direction at a time, all controlled by Prof. Pang's controller.

Prof. Pang's yard is a 2D plane. The robot needs to move from its current location $$$A$$$ to the destination $$$B$$$ to fulfill some "cleaning" needs of Prof. Pang. However, there are two straight walls $$$CD$$$ and $$$EF$$$ in Prof. Pang's yard. Since the robot is clumsy, it will fall over if it touches any of the walls (even at endpoints).

Now that Prof. Pang is lazy, he wants to minimize the number of times the robot changes its direction. Can you help him?

Prof. Pang is playing a card game with his two friends Alice and Bob. All cards are drawn from a standard 52-card deck. A standard 52-card deck comprises $$$13$$$ ranks in each of the four French suits: clubs ($$$\clubsuit$$$), diamonds ($$$\diamondsuit$$$), hearts ($$$\heartsuit$$$) and spades ($$$\spadesuit$$$). Each suit includes an Ace (A), a King (K), a Queen (Q), and a Jack (J), each depicted alongside a symbol of its suit; and numerals or pip cards from the Deuce (Two) to the Ten, with each card depicting that many symbols (pips) of its suit. No card can be drawn more than once.

Individual cards are ranked as follows (high-to-low): A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2. Suits do not affect ranks of the cards. For example, Ace of diamonds and Ace of clubs have the same rank. No one of them is ranked strictly higher than the other.

Initially, Alice and Bob will hold one or more cards while Prof. Pang will hold exactly one card. Each player can see cards held by himself/herself and cards held by other players. They will play the game in the following multi-round rule:

• The initiative player chooses one card and put it out to start one round.
• The next player can pass or put out a new card, then the player after the next can also pass or put out a new card, and so on. The only constraint is that the rank of the newly put card should be strictly higher than all previous cards in this round.
• The round ends when two players choose to pass consecutively. The one who put out the last card becomes the initiative player in the next round.
• If someone put out all the cards in his/her hand, the game ends immediately.

In this game, Alice is the initiative player in the first round. Bob, Prof. Pang, and Alice are the next players of Alice, Bob, and Prof. Pang respectively. Prof. Pang will be happy if and only if he is the one that first put out all the cards. (Prof. Pang wants to be happy, of course.) Alice wants to drink milk tea so she decides to make Prof. Pang happy and then asks him to buy milk tea for her. However, Bob doesn't want it to happen, so he decides to avoid Prof. Pang from being happy. If they play the game optimally for themselves, will Prof. Pang be happy in the end?

Prof. Pang has an annual leave of $$$c$$$ days and he wants to go on vacation.

Now there are $$$n$$$ days in a year. Prof. Pang can gain $$$a_i$$$ happiness if he rests on the $$$i$$$-th day. The values of happiness, $$$a_i$$$, may be negative.

Prof. Pang wants you to do $$$m$$$ operations:

• $$$1~x~y$$$, change the happiness of the $$$x$$$-th day to $$$y$$$.
• $$$2~l~r$$$, Prof. Pang wants to find a period of vacation in $$$[l, r]$$$. He wants to rest for several (possibly $$$0$$$) days in a row and gain as much happiness as possible. However, he only has $$$c$$$ days off, thus he can rest for no more than $$$c$$$ consecutive days in $$$[l,r]$$$.

  That means he wants to find $$$$$$\max\left(\max_{l \leq l' \leq r' \leq r\atop r'-l'+1\leq c} ~~ \left(\sum_{i=l'} ^{r'} a_i\right), 0\right).$$$$$$

Prof. Pang is given an $$$n\times m$$$ board. Some cells are colored black, some cells are colored white, and others are uncolored.

Prof. Pang doesn't like check patterns, so he wants to color all uncolored cells such that there is no check pattern on the board.

$$$4$$$ cells forming a $$$2\times 2$$$ square are said to have the check pattern if they are colored in one of the following ways:

Prof. Shou is given an $$$n\times m$$$ board. Some cells are colored black, some cells are colored white, and others are uncolored.

Prof. Shou likes check patterns, so he wants to color all uncolored cells and maximizes the number of check patterns on the board.

$$$4$$$ cells forming a $$$2\times 2$$$ square are said to have the check pattern if they are colored in one of the following ways:

Prof. Pang builds his famous coding team recently. To pursue a gold medal in ICPC, hundreds of pupils join his team. Unfortunately, one of Prof. Pang's students believes that for any integers $$$a$$$ and $$$b$$$, $$$a\times b\ge a+b$$$. To disprove this proposition, Prof. Pang writes $$$n$$$ numbers $$$a_1,a_2,\ldots, a_n$$$ on a paper and wants you to count how many pairs of numbers $$$(a_i, a_j)$$$ ($$$1\le i \lt j\le n$$$) satisfies $$$a_i\times a_j \lt a_i+a_j$$$.

Prof. Pang is getting addicted to the game called Elden Ring, in which the world is a connected graph including $$$n$$$ vertices indexed from $$$1$$$ to $$$n$$$ and $$$m$$$ undirected edges. Players start at vertex $$$1$$$ and travel across the world to slay the god on vertex $$$n$$$.

However, it's not that easy. For any vertex $$$i$$$ except vertex $$$1$$$, there is exactly one boss whose level is $$$l_i$$$, and the player starts the game with level $$$l_1$$$. For each day, the player can travel to any vertex $$$i$$$ from vertex $$$1$$$ and challenge the boss there. If the current level of the player is greater than the boss, the boss will be eliminated from the world (inactivated) and the level of the player will be increased by $$$A$$$. Notice that traveling through a vertex that has an active boss is forbidden. (In other words, Prof. Pang can travel from vertex $$$1$$$ to vertex $$$i$$$ if there is a path in the graph from vertex $$$1$$$ to vertex $$$i$$$ such that each vertex on this path, except for vertex $$$i$$$, has no active boss.) Meanwhile, at the beginning of each day, all the remaining bosses in the world will also be promoted by $$$B$$$ levels.

To finish a playthrough of the game, you need to slay the boss on vertex $$$n$$$ (Elden Beast). Given the information of the world, Prof. Pang is wondering how many days he needs at least to do so.

The Player can only challenge one boss each day.

Prof. Pang has an extraordinary vision. He can see the pixels on a 4K monitor. To test Prof. Pang's vision, Prof. Shou will show Prof. Pang several pixels and let Prof. Pang guess a straight line that contains these pixels. Given $$$k$$$ pixels with coordinates $$$(i, y_i)$$$ ($$$0\le i \lt k$$$), Prof. Pang must find nonnegative integers $$$a, b$$$ and $$$c$$$ (which represent the line $$$y=\frac{ax+b}{c}$$$) such that $$$y_i=\lfloor \frac{ai+b}{c} \rfloor$$$ for all $$$0\le i \lt k$$$.

Prof. Shou will ask Prof. Pang multiple questions. They are given as follows: Prof. Shou has a fixed array $$$x_1,\ldots, x_n$$$. For each question, Prof. Shou chooses a range in the array, $$$x_l,\ldots, x_r$$$. Then he defines $$$y_i=x_{l+i}$$$ for $$$0\le i\le r - l$$$ and asks Prof. Pang to answer the question for the $$$r-l+1$$$ pixels $$$(0, y_0), \ldots, (r-l, y_{r-l})$$$.

Please help Prof. Pang answer all the questions. For each question, output the answer with the minimum $$$(c, a, b)$$$ in lexical order.

It is guaranteed that the answer exists when Prof. Pang chooses the whole array $$$x_1, x_2, \dots, x_n$$$. So the answer always exists when Prof. Pang chooses an interval of this array.

Prof. Pang is giving a lecture on the Fenwick tree (also called binary indexed tree).

In a Fenwick tree, we have an array $$$c[1\ldots n]$$$ of length $$$n$$$ which is initially all-zero ($$$c[i]=0$$$ for any $$$1\le i\le n$$$). Each time, Prof. Pang can call the following procedure for some position $$$pos$$$ ($$$1\leq pos \leq n$$$) and value $$$val$$$:

def update(pos, val):
    while (pos <= n):
        c[pos] += val
        pos += pos & (-pos)

Note that pos & (-pos) equals to the maximum power of $$$2$$$ that divides pos for any positive integer pos.

In the procedure, $$$val$$$ can be any real number. After calling it some (zero or more) times, Prof. Pang forgets the exact values in the array $$$c$$$. He only remembers whether $$$c[i]$$$ is zero or not for each $$$i$$$ from $$$1$$$ to $$$n$$$. Prof. Pang wants to know what is the minimum possible number of times he called the procedure assuming his memory is accurate.

Near Prof. Pang's big house, there is an ant group which has $$$m$$$ ants and lives underground in a cave with $$$n$$$ holes. They get out of the holes for food. So where is the food? It should be in Prof. Pang's big refrigerator. The ants want to steal the food from the big refrigerator.

Specifically, for an ant, it needs $$$1$$$ second to leave from the cave through any hole and $$$1$$$ second to enter the cave through any hole. Different holes have different locations. The distance between the $$$i$$$-th hole and the refrigerator is $$$a_i$$$. Thus, after leaving the cave through the $$$i$$$-th hole, an ant needs $$$a_i$$$ seconds to go to the refrigerator. After stealing some food from the refrigerator, an ant needs $$$a_i$$$ seconds to go back to the $$$i$$$-th hole. Stealing food costs no time for the ants since they are skillful enough.

Each ant will leave the cave to steal something from the refrigerator and return to (enter) the cave after stealing. Each ant must leave the cave exactly once and then return to the cave. One ant can arbitrarily choose one hole to leave and also arbitrarily choose one hole to enter, where the two holes need not be the same. For any hole, during any second, there can be at most one ant leaving or entering the cave through it. There cannot be one ant leaving the cave and another ant entering the cave using the same hole during the same second. Because of this capacity constraint, some ants may need to wait before they leave the hole and/or before they return to the hole after stealing.

So you, Prof. Pang's good friend, need to calculate the minimum time cost for ants to achieve the goal and play a trick on Prof. Pang so that the ants can steal the food without being caught by Prof. Pang. The time cost is defined as the total length of time during which at least one ant is not in the cave. When an ant is entering or leaving the cave through some hole, it is not in the cave.