Monocarp plays a computer game. There are $$$n$$$ different sets of armor and $$$m$$$ different weapons in this game. If a character equips the $$$i$$$-th set of armor and wields the $$$j$$$-th weapon, their power is usually equal to $$$i + j$$$; but some combinations of armor and weapons synergize well. Formally, there is a list of $$$q$$$ ordered pairs, and if the pair $$$(i, j)$$$ belongs to this list, the power of the character equipped with the $$$i$$$-th set of armor and wielding the $$$j$$$-th weapon is not $$$i + j$$$, but $$$i + j + 1$$$.

Initially, Monocarp's character has got only the $$$1$$$-st armor set and the $$$1$$$-st weapon. Monocarp can obtain a new weapon or a new set of armor in one hour. If he wants to obtain the $$$k$$$-th armor set or the $$$k$$$-th weapon, he must possess a combination of an armor set and a weapon that gets his power to $$$k$$$ or greater. Of course, after Monocarp obtains a weapon or an armor set, he can use it to obtain new armor sets or weapons, but he can go with any of the older armor sets and/or weapons as well.

Monocarp wants to obtain the $$$n$$$-th armor set and the $$$m$$$-th weapon. What is the minimum number of hours he has to spend on it?

A permutation of length $$$n$$$ is an array $$$p=[p_1,p_2,\dots, p_n]$$$ which contains every integer from $$$1$$$ to $$$n$$$ (inclusive) exactly once. For example, $$$p=[4, 2, 6, 5, 3, 1]$$$ is a permutation of length $$$6$$$.

You are given three integers $$$n$$$, $$$a$$$ and $$$b$$$, where $$$n$$$ is an even number. Print any permutation of length $$$n$$$ that the minimum among all its elements of the left half equals $$$a$$$ and the maximum among all its elements of the right half equals $$$b$$$. Print -1 if no such permutation exists.

A wrestling club trains $$$n$$$ athletes. Each of them specializes either in algorithmic sambo (referred below as sport A), or in berland jiu-jitsu (referred below as sport B). In addition, each athlete has a certain level of skill.

Thus, the $$$i$$$-th athlete is characterized by two parameters: $$$t_i$$$ — a sport (either A or B) and an integer skill level $$$f_i$$$ ($$$-10^6 \le f_i \le 10^6$$$).

If an athlete from sport A competes in B, then their skill level is reduced by a given number $$$x$$$ (the value does not depend on a particular athlete). Similarly, if an athlete from sport B competes in A, then their skill level is reduced by a given number $$$y$$$ (again, the value does not depend on a particular athlete).

The club plans to participate in a competition. To participate, it is required to set up $$$k$$$ ($$$2k \le n$$$) teams of two athletes in each — one of them will compete in sport A, the other will compete in sport B. Of course, no athlete can be included in more than one team.

Your task is to compose $$$k$$$ teams in such a way that the total skill of all participating athletes in these teams is maximum possible. Formally, it is necessary to form $$$k$$$ teams from the $$$n$$$ given athletes, in each team there should be one athlete competing in A and one athlete competing in B. If an athlete competes in a sport they don't specialize in, then their skill decreases by $$$x$$$ (if an athlete with $$$t_i$$$ = A competes in B) or by $$$y$$$ (if an athlete with $$$t_i$$$ = B competes in A).

Print the maximum possible sum of skill levels of athletes in $$$k$$$ teams if the club forms teams in an optimal way. Remember that an athlete's skill level is reduced (by $$$x$$$ or $$$y$$$ depending on the sport) if they are playing in a sport that is different from their specialization.

You are given an array $$$c = [c_1, c_2, \dots, c_m]$$$. An array $$$a = [a_1, a_2, \dots, a_n]$$$ is constructed in such a way that it consists of integers $$$1, 2, \dots, m$$$, and for each $$$i \in [1,m]$$$, there are exactly $$$c_i$$$ occurrences of integer $$$i$$$ in $$$a$$$. So, the number of elements in $$$a$$$ is exactly $$$\sum\limits_{i=1}^{m} c_i$$$.

Let's define for such array $$$a$$$ the value $$$f(a)$$$ as $$$$$$f(a) = \sum_{\substack{1 \le i \lt j \le n\\ a_i = a_j}}{j - i}.$$$$$$

In other words, $$$f(a)$$$ is the total sum of distances between all pairs of equal elements.

Your task is to calculate the maximum possible value of $$$f(a)$$$ and the number of arrays yielding the maximum possible value of $$$f(a)$$$. Two arrays are considered different, if elements at some position differ.

Modern web systems have several layers of protection from attacks. One of such layers is request throttling, which is aimed to keep incoming request rate at a certain level and, therefore, protect the system from DDoS attacks.

Further on, we will consider a simplified IP-based throttling model. In this problem, we will work with IPv4 addresses only. Let's also assume that there are no reserved or internal addresses and the entire IPv4 address space is used.

The next five paragraphs give the formal definition of IPv4 address and IPv4 subnet, respectively. They also describe the structure of the IPv4 address space. These are standard definitions and properties, so if you are familiar with them, you can skip those paragraphs.

An IPv4 address is a 32-bit unsigned integer written in the form $$$a.b.c.d$$$, where each of the values $$$a,b,c,d$$$ is called an octet and is an integer from $$$0$$$ to $$$255$$$ written in decimal notation. For example, the IPv4 address $$$192.168.0.1$$$ can be converted to a 32-bit number using the following expression: $$$192 \cdot 2^{24} + 168 \cdot 2^{16} + 0 \cdot 2^8 + 1 \cdot 2^0$$$. The first octet $$$a$$$ encodes the most significant (leftmost) $$$8$$$ bits, the octets $$$b$$$ and $$$c$$$ — the following blocks of $$$8$$$ bits (in this order), and the octet $$$d$$$ encodes the least significant (rightmost) $$$8$$$ bits.

An IPv4 subnet of size $$$/x$$$ is represented as $$$a.b.c.d/x$$$ (where $$$0 \le x \le 32$$$). A subnet $$$a.b.c.d/x$$$ contains all IPv4 addresses with $$$x$$$ leftmost (most significant) bits equal to $$$x$$$ leftmost bits of the address $$$a.b.c.d$$$. It is required that $$$32 - x$$$ rightmost (least significant) bits of subnet $$$a.b.c.d/x$$$ are zeroes.

Naturally, it happens that all addresses matching subnet $$$a.b.c.d/x$$$ form a continuous range. The range starts with the address $$$a.b.c.d$$$ (its rightmost $$$32 - x$$$ bits are zeroes). The range ends with the address such that its $$$x$$$ leftmost bits equal to $$$x$$$ leftmost bits of address $$$a.b.c.d$$$, and all its $$$32 - x$$$ rightmost bits are ones. A subnet of size $$$/x$$$ contains exactly $$$2^{32-x}$$$ addresses.

For example:

• The subnet $$$192.168.0.0/24$$$ contains a range of $$$256$$$ addresses. $$$192.168.0.0$$$ is the first address of the range, and $$$192.168.0.255$$$ is the last one.
• The subnet $$$172.168.0.70/31$$$ contains two addresses: $$$172.168.0.70$$$ and $$$172.168.0.71$$$.
• The subnet $$$10.8.179.3/32$$$ contains only one address: $$$10.8.179.3$$$.

The entire IPv4 address space consists of $$$2^{32}$$$ IP addresses. In the terms of subnets, it means there are $$$2^{32}$$$ different $$$/32$$$ subnets (because each $$$/32$$$ subnet contains exactly one IP address), $$$2^{31}$$$ different $$$/31$$$ subnets (each $$$/31$$$ subnet contains two addresses), and so on, $$$2^1 = 2$$$ different $$$/1$$$ subnets, and $$$2^0 = 1$$$ subnet of size $$$/0$$$. Furthermore, it can be noted that each IP address is contained in exactly one subnet of each size from $$$/0$$$ to $$$/32$$$ inclusive. Further on, such subnets will be called parent subnets. E.g. these are some of the parent subnets of the IPv4 address $$$192.168.21.5$$$: $$$192.168.21.5/32$$$, $$$192.168.21.4/30$$$, $$$192.168.21.0/24$$$, $$$192.168.16.0/21$$$, $$$192.168.0.0/16$$$, $$$192.0.0.0/8$$$, $$$128.0.0.0/1$$$, $$$0.0.0.0/0$$$.

The request throttling model is described by $$$33$$$ integers $$$t_0, t_1, \ldots, t_{32}$$$ — the throttling limits for $$$/0, /1, \ldots, /32$$$ subnets, respectively. In other words, $$$t_j$$$ is the maximum number of requests from the certain subnet of size $$$/j$$$ which are allowed to bypass the throttling subsystem and reach other layers of the system. The throttling limit for each of $$$2^j$$$ subnets of size $$$/j$$$ is equal to the same number $$$t_j$$$, but passed request count is calculated separately for each individual subnet.

Incoming requests are processed one by one. When a request arrives, its source IP address is analyzed, and if the address is within the throttling limits of all $$$33$$$ of its parent subnets, then the request is allowed. It goes through the throttling system, increasing the passed request count for all its parent subnets. Otherwise, the request is blocked and the passed request count for no subnet is increased. We assume that a request is within the throttling limits of a subnet if and only if the passed request count of that subnet is strictly less than the throttling limit for the subnet (i.e. the value of $$$t_j$$$ for the corresponding size of the subnet).

Your task is to emulate the work of the throttling subsystem. You are given $$$n$$$ incoming requests, where each request is characterized by its source IP address $$$s_i$$$. The requests should be processed in the order they are given. For each request, print "a" (without quotes) if the request is allowed, and "b" (also without quotes) if the request is blocked.

You are given a pair of integers $$$(a, b)$$$ and an integer $$$x$$$.

You can change the pair in two different ways:

• set (assign) $$$a := |a - b|$$$;
• set (assign) $$$b := |a - b|$$$,

The pair $$$(a, b)$$$ is called $$$x$$$-magic if $$$x$$$ is obtainable either as $$$a$$$ or as $$$b$$$ using only the given operations (i.e. the pair $$$(a, b)$$$ is $$$x$$$-magic if $$$a = x$$$ or $$$b = x$$$ after some number of operations applied). You can apply the operations any number of times (even zero).

Your task is to find out if the pair $$$(a, b)$$$ is $$$x$$$-magic or not.

You have to answer $$$t$$$ independent test cases.

You are a usual chat user on the most famous streaming platform. Of course, there are some moments when you just want to chill and spam something.

More precisely, you want to spam the emote triangle of size $$$k$$$. It consists of $$$2k-1$$$ messages. The first message consists of one emote, the second one — of two emotes, ..., the $$$k$$$-th one — of $$$k$$$ emotes, the $$$k+1$$$-th one — of $$$k-1$$$ emotes, ..., and the last one — of one emote.

For example, the emote triangle for $$$k=3$$$ consists of $$$5$$$ messages:

Of course, most of the channels have auto moderation. Auto moderator of the current chat will ban you right after you spam at least $$$x$$$ emotes in succession (you can assume you are the only user in the chat). Now you are interested — how many messages will you write before getting banned? Or maybe you will not get banned at all (i.e. will write all $$$2k-1$$$ messages and complete your emote triangle successfully)? Note that if you get banned as a result of writing a message, this message is counted.

You have to answer $$$t$$$ independent test cases.

Monocarp is a tutor of a group of $$$n$$$ students. He communicates with them using a conference in a popular messenger.

Today was a busy day for Monocarp — he was asked to forward a lot of posts and announcements to his group, that's why he had to write a very large number of messages in the conference. Monocarp knows the students in the group he is tutoring quite well, so he understands which message should each student read: Monocarp wants the student $$$i$$$ to read the message $$$m_i$$$.

Of course, no one's going to read all the messages in the conference. That's why Monocarp decided to pin some of them. Monocarp can pin any number of messages, and if he wants anyone to read some message, he should pin it — otherwise it will definitely be skipped by everyone.

Unfortunately, even if a message is pinned, some students may skip it anyway. For each student $$$i$$$, Monocarp knows that they will read at most $$$k_i$$$ messages. Suppose Monocarp pins $$$t$$$ messages; if $$$t \le k_i$$$, then the $$$i$$$-th student will read all the pinned messages; but if $$$t \gt k_i$$$, the $$$i$$$-th student will choose exactly $$$k_i$$$ random pinned messages (all possible subsets of pinned messages of size $$$k_i$$$ are equiprobable) and read only the chosen messages.

Monocarp wants to maximize the expected number of students that read their respective messages (i.e. the number of such indices $$$i$$$ that student $$$i$$$ reads the message $$$m_i$$$). Help him to choose how many (and which) messages should he pin!

Monocarp is playing a modified version of Tetris game.

The game field is a rectangle divided into square cells. The rectangle contains $$$k$$$ rows (numbered $$$1$$$ through $$$k$$$ from bottom to top) and $$$10^9 + 1$$$ columns (numbered $$$0$$$ through $$$10^9$$$ from left to right). Initially, all cells are empty.

Initially, Monocarp's score in the game is $$$0$$$. To increase it, Monocarp can drop tetris pieces onto the game field. Each tetris piece is a rectangle with a certain width and a height equal to $$$1$$$. When the $$$i$$$-th piece appears on the game field, it initially occupies the cells from $$$l_i$$$ to $$$r_i$$$ (inclusive) in the $$$k$$$-th row of the field. After that, the piece starts falling: it moves one row down (i. e. stops occupying the cells in the current row and starts occupying the cells in the row right below the current one) until it either reaches the row $$$1$$$, or at least one of the cells directly below the piece is already occupied. Formally, if the piece is currently occupying the cells $$$[l_i, r_i]$$$ in the $$$j$$$-th row, it stops if and only if one of the following conditions is met:

• $$$j = 1$$$;
• at least one of the cells from $$$l_i$$$-th to $$$r_i$$$-th in the $$$(j-1)$$$-th row is already occupied.

Each tetris piece falls vertically downward, Monocarp cannot force them to move left or right (as it is possible in regular Tetris). While a tetris piece is falling, Monocarp cannot drop any new tetris pieces, he must wait until the current piece stops falling.

Monocarp can drop up to $$$n$$$ tetris pieces onto the game field. If the $$$i$$$-th piece is dropped, it initially occupies the cells from $$$l_i$$$ to $$$r_i$$$ in the $$$k$$$-th row (and if at least one of those cells is already occupied, the piece cannot be dropped); and dropping it increases Monocarp's score by $$$c_i$$$. Monocarp can drop any tetris pieces in any order, but each tetris piece can be dropped at most once.

What is the maximum possible score Monocarp can achieve?

Chess Grandmaster Hikaru Nakamura often plays chess on his favorite website. When a game starts, sometimes Hikaru feels like playing a normal game of chess. But in some cases, to make things a bit interesting and tricky, he plays the Bongcloud opening, which is an atrociously bad way to start a game of chess, but may throw some of his opponents off their game plans.

Today, Hikaru is going to play $$$n$$$ games of chess. Initially, his rating is $$$x$$$. If he defeats his opponent in the $$$i$$$-th game, his rating goes up by $$$a_i$$$ points; if he loses to the $$$i$$$-th opponent, his rating goes down by $$$b_i$$$ points (we assume that draws won't happen at all). The order of Hikaru's opponents cannot be changed. For each opponent, Hikaru knows the result of the game with him even before all the games start, though this result may be different if Hikaru plays Bongcloud instead of a normal game of chess. Formally, for the $$$i$$$-th opponent, two integers $$$c_i$$$ and $$$d_i$$$ are given: $$$c_i = 1$$$ means Hikaru defeats his opponent in a normal game of chess, $$$c_i = 0$$$ means he loses in a normal game; the number $$$d_i$$$ represents the result of the game if Hikaru plays the Bongcloud opening in a same way.

Now, Hikaru has some specific rules to decide whether to start a normal game or a Bongcloud game:

• if Hikaru's current rating is less than $$$x - k$$$, he plays a normal chess game;
• if Hikaru's current rating is greater than $$$x + k$$$, he plays with the Bongcloud opening;
• if none of those two conditions apply, Hikaru can choose either way to play a game.

What is the maximum possible rating Hikaru can achieve after all $$$n$$$ games?

Polycarp is a huge fan of ice cream. However, he lives in a small city of Bertown, where it's pretty hard to find new types of ice cream to try out.

Luckily for Polycarp, an ice cream van will be arriving to Bertown every day during the next $$$n$$$ days. Each day, the van will be bringing an infinite supply of one type of ice cream. The type of ice cream brought on the $$$i$$$-th day has a taste value of $$$a_i$$$.

Now Polycarp wants to come up with an integer value $$$x$$$ (the same for all $$$n$$$ days) and divide the types of ice cream into tasty and mediocre — an ice cream type will be considered tasty if its taste value is not less than $$$x$$$, otherwise it's mediocre. He proceeds with the following strategy on the $$$i$$$-th of the next $$$n$$$ days:

• if Polycarp has at least one ice cream left from previous days, he doesn't buy any ice cream on that day;
• otherwise, if $$$a_i \lt x$$$ (the ice cream that is being sold during this day is mediocre), then he buys $$$1$$$ ice cream and eats it on the $$$i$$$-th day;
• otherwise, he buys $$$k_i$$$ ice creams and eats one of them on each of the days $$$i, i+1, \dots, i+k_i-1$$$. He doesn't buy any more ice creams during these days. Thus, the next time he will visit the van on the day $$$i+k_i$$$, if that day doesn't exceed $$$n$$$. Note that $$$i+k_i$$$ might exceed $$$n$$$ — in that case, Polycarp still eats all $$$k_i$$$ ice creams he has already bought.

Polycarp estimates his happiness as the total taste value of the ice creams he eats. In particular, if he eats $$$k_i$$$ ice creams of the $$$i$$$-th type, then its taste value $$$a_i$$$ gets added to the happiness $$$k_i$$$ times.

What is the maximum happiness Polycarp can achieve by choosing the value of $$$x$$$?

Vitaly is the mayor of Bertown. He prepares for the new mayor election. As a part of his election campaign, he states that he will make Bertown clean again.

There's not that much time till the election starts, so Vitaly's PR manager Arkady decided to clean only the trash resided in the central street of the city. Namely, there are $$$n$$$ dirty places on the central street, numbered from $$$1$$$ to $$$n$$$ from west to east. Arkady wants to dispose of the trash in the $$$i$$$-th place during the $$$i$$$-th day.

As a true patriot of Bertown and the only person in Vitaly's team who is good in arithmetic, you were asked to calculate the minimal number of people to be involved in the cleaning process. This number is selected once before the process starts and stays the same during all $$$n$$$ days.

After talking to a cleaning expert, you realized that one worker can perform one of three actions during day $$$i$$$:

• dispose of $$$1$$$ kilogram of trash in the place $$$i$$$;
• move exactly $$$2$$$ kilograms of trash from the place $$$i$$$ to the place $$$i + 1$$$ (of course, this is impossible if $$$i = n$$$);
• do nothing.

The street is considered clean if there's no trash in all places at the end of the $$$n$$$-th day. Thus, Arkady has to hire multiple people, so that they can work simultaneously to clean the street.

Help Arkady to calculate the minimal number of people to be involved in the cleaning process.

Let's denote the Manhattan distance between two points $$$p_1$$$ (with coordinates $$$(x_1, y_1)$$$) and $$$p_2$$$ (with coordinates $$$(x_2, y_2)$$$) as $$$d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|$$$. For example, the distance between two points with coordinates $$$(1, 3)$$$ and $$$(4, 2)$$$ is $$$|1 - 4| + |3 - 2| = 4$$$.

You are given two points, $$$A$$$ and $$$B$$$. The point $$$A$$$ has coordinates $$$(0, 0)$$$, the point $$$B$$$ has coordinates $$$(x, y)$$$.

Your goal is to find a point $$$C$$$ such that:

• both coordinates of $$$C$$$ are non-negative integers;
• $$$d(A, C) = \dfrac{d(A, B)}{2}$$$ (without any rounding);
• $$$d(B, C) = \dfrac{d(A, B)}{2}$$$ (without any rounding).

Find any point $$$C$$$ that meets these constraints, or report that no such point exists.

A haiku is a Japanese form of poetry. All haiku poems follow a distinct pattern: they consist of three phrases — the first phrase has $$$5$$$ syllables, the second phrase has $$$7$$$ syllables and the third phrase has $$$5$$$ syllables.

Phonetic nuances aside, let's consider each vowel in a phrase a single syllable. Thus, a phrase contains as many syllables as vowels.

From that, there arises a classic argument of what is considered a vowel. Letters A, E, I, O, U are vowels for sure (regardless of being lowercase or uppercase). Letter Y, however... Let's say that it can be both vowel or consonant, and you are free to decide which one you want it to be each time it appears in the phrase. All other letters are consonants.

You want to check if the given three phrases can fit into the haiku format. That is if it's possible to call every letter Y in them a vowel or a consonant in such a way that the number of syllables in the phrases is $$$5-7-5$$$.