As shown in the figure, in the land of Bugcats, there is a Bugcat chat software containing 7 types of memes. Each meme has three attributes:

• ID: an integer from $$$1$$$ to $$$7$$$.
• Abbreviation (abbr.): a string that starts with '/' and contains only lowercase letters apart from the leading '/'.
• Description: a string consisting of lowercase letters and hyphens '-'.

Now a Bugcat sends you a string. As the maintainer of the software, you need to determine whether the string is an abbreviation or a description, and also find its corresponding ID.

Note that the string sent by the Bugcat is guaranteed to be the abbreviation or description of one of the 7 memes in the table.

There is a creature known as Bugcat who wants to play a counting game. At the start of the game, Bugcat chooses a fixed integer $$$k$$$. Then, starting from $$$1$$$, Bugcat begins counting upwards, but it will only call out a number if it meets at least one of the following conditions:

1. The number is a multiple of $$$k$$$.

2. The digit $$$k$$$ appears in the decimal representation of the number.

Bugcat wants to know what the $$$x$$$-th number it calls out will be. Since Bugcat is a bit slow and can only count one by one, it has tasked you with finding the answer.

Bugcat is currently managing a queue. Bugcat has a specific preference: it does not want any duplicate numbers to appear in the queue at the same time. Additionally, all numbers entering the queue must be within the range $$$[1, m]$$$.

You need to process $$$Q$$$ operations. There are three types of operations:

• Type $$$1$$$ (Push): Attempt to add the integer $$$x$$$ to the back of the queue. If $$$x$$$ is already present in the queue, do nothing. Otherwise, add $$$x$$$ to the tail.
• Type $$$2$$$ (Pop): Remove the element at the head of the queue. It is guaranteed that the queue is not empty when this operation is called.
• Type $$$3$$$ (Query): Find the $$$x$$$-th number currently in the queue (indexed from $$$1$$$, where $$$1$$$ is the head). If the queue contains fewer than $$$x$$$ elements, output $$$-1$$$.

Your task is to output the result for every Type $$$3$$$ operation.

There are $$$n$$$ elements $$$a_1, a_2, \dots, a_n$$$, each with a lock. Initially, all elements are unlocked.

Given $$$q$$$ queries, the $$$i$$$-th query consists of four integers $$$(t_s, t_e, l, r)$$$, where $$$1 \le l \le r \le n$$$. Each query performs a locking process and an unlocking process on the timeline.

Locking process: Starting from time $$$t_s$$$, in the next $$$r-l+1$$$ time instants, the elements $$$a_l, a_{l+1}, \dots, a_r$$$ are processed in order. Specifically, at time $$$t_s + k$$$, element $$$a_{l+k}$$$ is processed ($$$0 \le k \le r-l$$$). If this element is currently unlocked, it is locked, and the lock is marked as belonging to the current query; if it is already locked by another query, no operation is performed. That is, if when accessing this lock, it has already been locked by another locking process, this lock will not have any changes.

Unlocking process: Starting from time $$$t_e$$$, in the next $$$r-l+1$$$ time instants, the elements $$$a_l, a_{l+1}, \dots, a_r$$$ are processed in order. Specifically, at time $$$t_e + k$$$, element $$$a_{l+k}$$$ is processed ($$$0 \le k \le r-l$$$). If the current lock on this element was added by this query during the locking process, it is unlocked; otherwise, no operation is performed.

For all operations occurring at the same time on the same element, they are executed in ascending order of query index.

For each query, count the number of elements that were successfully locked during its locking process.

Two Bugcats are planning to meet up for a gathering. The map they live on consists of $$$n$$$ nodes and $$$m$$$ directed edges. The first Bugcat starts at Node $$$1$$$, and the second Bugcat starts at Node $$$n$$$.

Each edge $$$i$$$ connects node $$$x_i$$$ to node $$$y_i$$$. There are two ways to traverse an edge:

• Walking: This consumes $$$z_i$$$ units of stamina.
• Taking a Taxi: This costs $$$1$$$ dollar but consumes $$$0$$$ stamina.

The two Bugcats have a combined total budget of $$$w$$$ dollars. They can choose to take a taxi on any edge at any time, provided they do not exceed their total budget.

Your task is to find the minimum total stamina the two Bugcats must consume in order to meet at the same node, given their budget constraint.If it is impossible for the two Bugcats to meet, output $$$-1$$$.

Little Z is playing a card game. He has $$$N$$$ cards stacked face-up in a pile. Each card has a single uppercase letter printed on its face.

The game requires him to rearrange the cards into a new pile, such that the sequence of letters from top to bottom of the new pile is lexicographically smallest.

Each time, Little Z can only take a card from either the top or the bottom of the current pile, and place it onto the bottom of the new pile. This operation is repeated until all cards have been moved to the new pile.

Given the initial sequence of letters from top to bottom, help Little Z find the lexicographically smallest sequence he can obtain.

This is an interactive problem.

In a layered defense system, there is an $$$n \times m$$$ grid. Rows are numbered $$$1$$$ to $$$n$$$ from top to bottom, and columns are numbered $$$1$$$ to $$$m$$$ from left to right. Some cells initially contain obstacles.

An invading drone starts from an empty cell in row $$$n$$$ and attempts to break through upward. You need to place additional obstacles to intercept it before it reaches row $$$1$$$.

Suppose the drone is currently at cell $$$(r, c)$$$. If $$$r \gt 1$$$, it moves upward one row in this round, and its target can only be one of the following three positions: $$$(r - 1, c - 1)$$$, $$$(r - 1, c)$$$, $$$(r - 1, c + 1)$$$. The cell it moves to must satisfy:

• It is within the board boundaries;
• There is no obstacle in that cell.

If the drone reaches row $$$1$$$, it is considered to have successfully broken through, and your program fails.

After each move of the drone, if it is currently at $$$(r, c)$$$ with $$$r \gt 1$$$, you may place at most one new obstacle. If you choose to place one, the obstacle must be placed in a currently empty cell $$$(x, y)$$$ satisfying $$$x \in \{r - 1, r - 2\}$$$, $$$1 \le x \le n$$$, $$$1 \le y \le m$$$. That is, you can only add an obstacle in the first or second row above the drone's current position. Newly placed obstacles remain permanently; you may also choose not to place any obstacle in that round.

Your goal is to make the drone unable to perform a move at some moment, thereby intercepting it successfully.

It is guaranteed that for every test case, there exists at least one strategy that ensures you can intercept the drone before it reaches row $$$1$$$.

After reading the input, you repeatedly perform the following interaction until the process ends:

1. Output two integers $$$x\ \ y$$$.
   • If $$$(x, y) = (0, 0)$$$, it means you choose not to place an obstacle in this round;
   • Otherwise, it means you place a new obstacle at cell $$$(x, y)$$$. In this case the following must hold:
     • The cell is within the board boundaries;
     • The cell currently contains no obstacle;
     • If the drone is currently in row $$$t$$$, then you must have $$$x \in \{t - 1, t - 2\}$$$.
2. Then the interactor moves the drone one step and outputs two integers $$$r$$$ and $$$c$$$:
   • If $$$(r, c) = (0, 0)$$$, the drone can no longer make a move, meaning you have successfully intercepted it. Your program should terminate immediately;
   • If $$$(r, c) = (-1, -1)$$$, you have failed to intercept it. This happens when the drone has already reached row $$$1$$$ or your output was invalid. Your program should terminate immediately, and you will receive Wrong answer;
   • Otherwise, the drone has moved to cell $$$(r, c)$$$, and the next round begins.

If your program continues interacting after reading $$$(0, 0)$$$ or $$$(-1, -1)$$$, or fails to follow the interaction protocol, you will also receive Wrong answer.

After outputting, flush the output buffer; otherwise you may get Idleness limit exceeded. For example:

• C/C++: fflush(stdout) or cout.flush()
• Java: System.out.flush()
• Python: sys.stdout.flush()

As a student of The Chinese University of Hong Kong, Shenzhen, Little B got lost when entering the teaching building for the first time (because TB is above TC, and TC is above TD). Years later, Little B became the designer of the new campus teaching building, and now he is designing the cross-sectional view of the building.

The new teaching building will have $$$2n$$$ teaching areas, numbered from $$$1$$$ to $$$2n$$$. The designed footprint length is $$$2n$$$ units, and the building height is limited to $$$n + 1$$$ units, meaning that the cross-sectional view can be regarded as an $$$(n + 1) \times (2n)$$$ grid. Each grid point must contain a number from $$$0$$$ to $$$2n$$$. $$$1 \sim 2n$$$ indicates the teaching area number at that position, and $$$0$$$ means that the position does not belong to any teaching area. Each teaching area must be 4-connected* in the cross-sectional view.

Let $$$a_{i,j}$$$ denote the teaching area number at the grid point in the $$$i$$$-th row and $$$j$$$-th column. We say that teaching area $$$x$$$ is above teaching area $$$y$$$ ($$$x \ne y$$$) if there exist $$$i, j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le 2n$$$) such that $$$a_{i, j} = x$$$, $$$a_{i + 1, j} = y$$$.

For structural clarity and elegance, Little B has determined $$$(2n - 1)$$$ relations. The $$$i$$$-th relation is of the form "teaching area $$$x_i$$$ is above teaching area $$$y_i$$$". If we add a directed edge from $$$x_i$$$ to $$$y_i$$$, the $$$2n$$$ teaching areas exactly form a downward tree** rooted at teaching area $$$1$$$.

Now, you need to design a valid cross-sectional view (i.e., assign a teaching area number to each grid cell) such that the directed graph corresponding to this cross-sectional view is exactly the same as the tree given by Little B. (That is, the relationships specified by Little B must be satisfied, while the relationships not specified by Little B must not be satisfied.)

Please output any valid filling scheme, or report that no solution exists.

*4-connected: A set of grid points is called 4-connected if any two points in the set can be connected by a sequence of adjacent (up, down, left, right) grid points that also belong to the set.

**Downward tree: A rooted tree with a specified root, where every edge is directed from the parent to the child (i.e., from the upper level to the lower level). In this problem, the given $$$2n - 1$$$ relations "teaching area $$$x_i$$$ is above teaching area $$$y_i$$$" correspond to directed edges $$$x_i \to y_i$$$, and these edges form a downward tree rooted at $$$1$$$.

Bugcat is playing a game. The game provides an undirected graph where each node contains a monster. A monster may also have zero or one minion. A node is considered unlocked only after you defeat all enemies (including the minion, if it exists) at that node. You can move to a node if and only if it is connected to at least one already unlocked node.

However, you do not necessarily need to defeat all enemies when you visit a node. Specifically, you may choose to defeat only the monster's minion and then leave for other nodes. In this case, the node remains locked.

The player starts with an initial HP $$$x$$$. When attempting to kill an enemy with HP $$$y$$$, if $$$x \ge y$$$, the enemy is defeated and the player's HP increases by $$$y$$$ (i.e., $$$x \leftarrow x + y$$$). Otherwise, the player dies immediately.

Maomaochong asks for your help. He provides the undirected graph and the initial HP of the monster at each node (initially, no monsters have minions). There are multiple operations of two types:

1. The monster at node $$$x$$$ summons a minion with HP $$$y$$$ (it is guaranteed that each monster at node $$$x$$$ will summon at most one minion throughout the game).
2. Given a starting node $$$x$$$ and an initial HP $$$y$$$, calculate the maximum possible final HP the player can achieve.

During the Lunar New Year, Bugcat has been playing a Mahjong-themed "roguelike" game (similar to Balatro). In this game, Bugcat draws tiles from a deck and discards them, and it has perfect knowledge of the tile sequence in the "wall" (the deck).

Bugcat starts wondering: if there is a Mahjong set with $$$n$$$ distinct types of tiles, what is the expected number of tiles drawn (including the initial $$$13$$$ tiles) to complete a "Four Concealed Pongs" (Sūankō) hand, assuming optimal play? Output the result modulo $$$10^9 + 7$$$.

Definitions:

• The Mahjong set: There are $$$n$$$ types of tiles. Each type has exactly $$$4$$$ identical-looking but distinct tiles. Thus, there are a total of $$$4n$$$ tiles in the deck.
• Four Concealed Pongs: A "Pong" (or triplet) is defined as $$$3$$$ tiles of the same type. To complete this hand, you need four Pongs and one pair ($$$2$$$ tiles of the same type).

Simplified Problem Statement:

There are $$$4n$$$ tiles, categorized into $$$n$$$ colors (types), with $$$4$$$ tiles per color. Even tiles of the same color are considered distinct.

Consider all $$$(4n)!$$$ possible permutations of the deck. For a given permutation, let the "cost" be the smallest index $$$i$$$ such that among the first $$$i$$$ tiles in the sequence, the following two conditions are met:

• At least $$$4$$$ colors have appeared $$$3$$$ or more times.
• At least $$$5$$$ colors have appeared $$$2$$$ or more times.

Find the expected value of the cost $$$i$$$ over all possible permutations. Output the result modulo $$$10^9 + 7$$$.

A tree by the river can be described as a form with $$$x$$$ nodes numbered $$$1 \sim x$$$:

• There is exactly one root, numbered $$$1$$$.
• For each node $$$i$$$ ($$$i \ne 1$$$), it has exactly one parent numbered $$$f$$$, satisfying $$$f \lt i$$$.

Little B cannot remember such an abstract concept as a "tree", so he invented two ways to turn a tree into a permutation:

• Method 1, $$$type = 1$$$: Start from the root, visit the parent first, then the children, and children are visited in increasing order of their numbers.
• Method 2, $$$type = 2$$$: Start from the root, visit the parent first, then the children, and children are visited in decreasing order of their numbers.

It can be proved that after visiting all nodes, the elements in $$$q$$$ form a permutation of $$$1 \sim x$$$.

A permutation is called ambiguous if it can be obtained from some tree $$$t_1$$$ by method 1 and also from some tree $$$t_2$$$ by method 2. Note that the two trees may be identical, i.e., $$$t_1$$$ may equal $$$t_2$$$.

The bugcat only remembers the positions of $$$1 \sim n$$$ in a permutation $$$a$$$ of length $$$n + m$$$, and asks you to determine, among all possible permutations, how many are ambiguous.

There are $$$2 ^ n$$$ bugcats, each with a distinct attribute that can be represented as a number from $$$0$$$ to $$$2 ^ n - 1$$$.

These bugcats are to be paired into $$$2 ^ {n - 1}$$$ groups (each group contains exactly two bugcats) to dine in the restaurant. The bugcats are kind-hearted, so no bugcat appears in more than one group.

The restaurant has $$$2 ^ {n - 1} + 1$$$ tables for two, numbered from $$$1$$$ to $$$2 ^ {n - 1} + 1$$$. It is required that the XOR of the attribute values of the two bugcats at each table equals the table number.

However, Little B, who came to the restaurant alone, has already taken the quietest table $$$x$$$. (That is, table numbered $$$x$$$ cannot be used by the bugcats.)

Can you provide a pairing such that all bugcats in different groups can be seated at different tables for two, and Little B does not move?