In this task, you are going to determine whether Nai is ambidextrous, i.e. whether he can write equally well with both hands.

You have learned that Nai writes at speed $$$L$$$ characters per minute with his left hand and at speed $$$R$$$ characters per minute with his right hand. If $$$L = R$$$, then obviously Nai writes equally well with both hands; but we allow some leniency.

Given a parameter $$$P$$$, where $$$50 \le P \le 100$$$, Nai is considered ambidextrous if the writing speed of his weaker (slower) hand is at least $$$P\%$$$ that of his dominant (faster) hand, or if $$$L = R$$$, in which case it is hard to tell which hand is dominant. Otherwise, he is either left- or right-handed.

This simple task should not take you more than a few minutes, right?

Bob the builder wants to build the most exciting roller coaster in the world!

Due to the limited space, Bob can only build the railroad without turning left or right. Also, Bob thinks the only interesting part of roller coaster is going down, so he will not consider any parts of the railroad going upward as well.

Under the above conditions, you may consider the railroad as a polyline (broken line) on a 2D Cartesian coordinate plane. Formally, Bob has to build the railroad from $$$x=0$$$ to $$$x=N$$$. For each integer $$$x=i$$$ ($$$0\le i\le N$$$), Bob can choose the height $$$H_i$$$ of the railroad as any non-negative integer. In other words, the railroad is a polyline formed by the points $$$(0, H_0), (1, H_1), \dots, (N, H_N)$$$ (in this order), with the constraints that:

• For safety reasons, the railroad should not be too steep, so for integers $$$i$$$ ($$$0\le i \lt N$$$), $$$H_{i + 1}=H_i$$$ or $$$H_{i + 1}=H_i - 1$$$.
• To let the passengers leave on the ground, $$$H_N=0$$$.

An example with $$$N=9$$$ and $$$H_{0..9}=\{4, 4, 3, 3, 3, 2, 2, 1, 1, 0\}$$$

To build an exciting roller coaster, Bob defines the exciting index as the number of times the passengers seeing new furthest part of the railroad. Formally:

• The passengers ride in positive $$$x$$$ direction (i.e. from $$$x=0$$$ to $$$x=N$$$), along the railroad.
• For integers $$$i$$$ ($$$0\le i\le N$$$), when passengers are at the point $$$(i, H_i)$$$, the furthest part of railroad they can see is defined the largest integer $$$f_i$$$ ($$$i\le f_i\le N$$$) such that there DO NOT EXIST any integers $$$j$$$ ($$$i \lt j \lt f_i$$$) that the point $$$(j, H_j)$$$ is strictly above the line segment formed by $$$(i, H_i)$$$ and $$$(f_i, H_{f_i})$$$. In this example, passengers at the point $$$(1, H_1)$$$ cannot see the point $$$(6, H_6)$$$ as there exists point $$$(4, H_4)$$$ lying strictly above the line segment formed by $$$(1, H_1)$$$ and $$$(6, H_6)$$$. However, they can see the point $$$(4, H_4)$$$ as there are no points lying strictly above the line segment formed by $$$(1, H_1)$$$ and $$$(4, H_4)$$$.

• For integers $$$i$$$ ($$$0\le i\le N$$$), if the value of $$$f_i$$$ is strictly greater than $$$f_k$$$ for all integers $$$k$$$ ($$$0\le k \lt i$$$), then point $$$(i, H_i)$$$ is considered as an exciting point. In particular, $$$(0, H_0)$$$ is an exciting point.
• The exciting index of the railroad is the number of exciting points.

An example with $$$f_{0..9}=\{1, 4, 4, 4, 8, 6, 8, 8, 9, 9\}$$$ and exciting index = 4

(Note that $$$f_4=8$$$ as $$$(6, 2)$$$ is just lying on the line segment formed by $$$(4, 3)$$$ and $$$(8, 1)$$$, but NOT "strictly above")

Given the value of $$$N$$$, please write a program to help Bob finding any valid design maximizing the exciting index.

"Captain Teemo on duty!"

"Hut two three four" Perhaps Teemo loves consecutive numbers as many people do.

Tristana, as a lover of consecutive numbers (and also Teemo), asked you $$$Q$$$ questions. For each question, you have to determine whether the given number $$$X$$$ can be represented as a sum of at least two consecutive positive integers. For example, the answer for $$$X=9$$$ is Yes as $$$9=2+3+4$$$ while the answer for $$$2$$$ is No (note that $$$(-1)+0+1+2=2$$$ is invalid as only positive integers are allowed).

Write a program to differentiate a polynomial in x.

Here's how to differentiate a polynomial in the form

$$$c_nx^n+c_{n-1}x^{n-1}+\cdots+c_1x+c_0$$$

Each term $$$c_ix^i$$$ where $$$i \ge 1$$$ can be handled individually:

1. Multiply the coefficient $$$c_i$$$ by $$$i$$$.
2. Decrease the exponent of $$$x$$$ by 1.
3. Therefore, the result of the term is $$$(c_i\times i)x^{i-1}$$$

Finally, join the results of the terms together to form the final polynomial. Also, the derivative of the constant term is 0.

For example, the derivative of $$$-3x^3+5x^2-7x+4$$$ is $$$(-3\times 3)x^{3-1}+(5\times 2)x^{2-1}+(7\times 1)x^{1-1}+0$$$ = $$$-9x^2+10x-7$$$

The polynomial's format is similar to the requirements for math homework:

• The polynomial does not start with a plus sign.
• The polynomial contains no spaces.
• The terms should be ordered in strictly decreasing degree of $$$x$$$.
• There should be no redundant terms. The term is omitted if the coefficient is 0.
• The 1 is omitted if the coefficient is 1 or -1. (see sample 1)
• The degree is written directly after x. The exponent is omitted if the degree is 1.
• The constant term is omitted if it is zero, except that when the whole polynomial is zero (see sample 3).

Percy is a primary school student. He is learning how to do addition and subtraction. Being a smart boy, he decided to use a calculator instead of doing it by hand.

The calculator can only store and display non-negative integers of up to 8 digits, i.e. integers between 0 and 99999999 inclusive. If at any time the result of an operation exceeds this range, the calculator will display Error and stops functioning. Therefore, Percy tries to rearrange the terms in the expression he is trying to calculate.

Specifically, the expression contains $$$N$$$ numbers between -99999999 and 99999999 and Percy needs to sum them up using the calculator one by one. Since numbers can be summed up in any order, help Percy find an order that won't cause any error.

Like in many countries, there is a football league in Hackerland. The top league (called Tourist League) has $$$N$$$ teams, where $$$N$$$ is an even number. The teams are conveniently numbered from $$$1$$$ to $$$N$$$.

For those unfamiliar with football leagues, here is the basic information that you need to know for this task. Three statistics determine a team's standing: points, goals scored, and goals conceded. For every match a team plays, they score goals and concede goals.

• If they score more goals than they concede, then they win and earn three points.
• If they score the same number of goals as they concede, then they draw and earn one point.
• If they score fewer goals then they concede, then they lose and earn no points.

For two teams $$$A$$$ and $$$B$$$, let $$$P_A$$$ be the total points team $$$A$$$ has, $$$S_A$$$ be the total number of goals scored by team $$$A$$$, and $$$C_A$$$ be the total number of goals conceded by team $$$A$$$. Likewise for $$$P_B$$$, $$$S_B$$$, and $$$C_B$$$. Team $$$A$$$ is ranked higher than team $$$B$$$ if and only if one of the following is true:

• $$$P_A \gt P_B$$$ (more points)
• $$$P_A = P_B$$$ and $$$S_A - C_A \gt S_B - C_B$$$ (same points, superior goal difference)
• $$$P_A = P_B$$$, $$$S_A - C_A = S_B - C_B$$$, and $$$S_A \gt S_B$$$ (same points, same goal difference, more goals scored)

There is no further tiebreaker. Therefore, it is possible for two teams to have the same rank. A team's rank is given by $$$1 + $$$ (number of teams ranked higher than it).

The final fixture in the league is always the most exciting one, especially at the top and at the bottom of the table, where teams fight fiercely for their respective targets. More important, all matches will start at the same time, and a team's fate may depend on scorelines of matches played hundreds of miles away!

For all $$$N$$$ teams in the Tourist League, you know their points, goals scored, and goals conceded, right before the final fixture. You also know the pairing for the final fixture.

Here is your task: based on your data, determine each team's best and worst final rank. For the sake of this task, there is no upper limit on the number of goals a team can score within a match; even a $$$10^9-0$$$ scoreline is considered possible.

The given data (points, goals scored, goals conceded) may be inconsistent, since they come from a questionable source. Nevertheless, you are to make predictions based on the data.

The pairing is guaranteed to be consistent, i.e. each team will play against exactly one other team.

One day, GFRIEND members went to a Go club to perform their song and learn how to play Go.

[video]output.mp4[/video]

To teach them the basic rules of Go, the master gave them $$$N$$$ white stones and $$$M$$$ black stones. He then ask them to use the white stones to surround the black stones on the standard 19x19 Go board. The arrangement must satisfy the followings:

• They must use all $$$N$$$ white stones and all $$$M$$$ black stones.
• All black stones must be "captured". In order to capture a group of black stones, it must be surrounded by white stones in all 4 directions without gaps and spaces.
• Though it is not necessary for the black stones to form a single group, all white stones must be necessary, i.e. removing any one white stone will cause at least one black stone not being captured.

The above rules can also be expressed by the followings:

• The 19x19 board must contain exactly $$$N$$$ white stones and exactly $$$M$$$ black stones.
• Each white stone must be directly adjacent to (4 directions) at least 1 black stone.
• Each black stone must be directly adjacent to (4 directions) 4 black or white stones.

Help GFRIEND by writing a program to find out if there is a possible arrangement, and if there is, output any one.

In Hackerland, sports programming is the most popular activity. More than half of its residents has a rating on Hackforces, the official programming competition platform there.

What is so unique about Hackforces is that 1-versus-1 matches are available! Two players can match online and enjoy a battle of wits anytime. The match can be boring though, if, for example, an absolute beginner with rating $$$1$$$ fights a Legendary Grandmaster with rating $$$10^9$$$ - everyone knows the outcome before the match starts.

Therefore, Hackforces has a handicap system, allowing the higher-rated player to play with some disadvantages, thus making the match more even. There are $$$N$$$ types of handicaps, and the $$$i$$$-th one is equivalent to reducing one's rating by $$$D[i]$$$ points. Here are some of them:

• Type With One's Nose - Self-explanatory.
• You Only Submit Once - Only one submission attempt per task.
• Blindfolded - Code while wearing a blindfold.

Seeing that many strong programmers do not voluntarily select a suitable handicap, Hackforces would like to install an auto-handicap feature. Given the ratings of two players $$$X$$$ and $$$Y$$$ ($$$X \le Y$$$), auto-handicap should automatically pick an index $$$i$$$ between $$$1$$$ and $$$N$$$ (inclusive), such that $$$Y - D[i] \gt 0$$$ and $$$|Y - D[i] - X|$$$ is minimized. In other words, the new rating $$$Y_{new} := Y - D[i]$$$ of the second player should be positive and as close to $$$X$$$ as possible.

There are three subtle details to keep in mind. First, if playing without handicap yields the smallest rating difference, then it is preferred to play without handicap. Second, if none of the handicaps can make $$$Y_{new}$$$ positive, then playing without handicap is the only choice. Third, if two or more different valid handicaps yield the same rating difference, then the one with the smallest index is preferred.

You are to implement this feature to pick the best handicap for $$$Q$$$ matches, according to the rules above.

Byteland is a country consisting of $$$N$$$ cities, numbered from $$$1$$$ to $$$N$$$, and they are connected by $$$M$$$ bidirectional roads. It is possible to reach each city from any other. Each road connects two cities $$$a$$$ and $$$b$$$. Two cities are neighbor if and only if they are directly connected by a road.

Scientists in Byteland found out that there will be an outbreak of Virus B in the coming weeks. The virus will first appear in one of the $$$N$$$ cities, make it into an infected city. Then, on each day the virus will spread to exactly one uninfected city which is neighbor to an infected city. the The infection process will end when all $$$N$$$ cities become infected.

As Virus B is a fatal and strong virus, they want to make some precautions against Virus B to minimize the impacts. Luckily, the scientists found out that Virus B has similar DNA structure with another Virus A, which appeared in Byteland 100 years ago, so the scientists predict that Virus B will infect different cities in a similar way as Virus A. More precisely, let the order of cities infected by Virus A be $$$A_1, A_2,\dots ,A_N$$$ and the order of cities infected by Virus B be $$$B_1, B_2, \dots, B_N$$$, the scientists predict that $$$B$$$ will be the lexicographically smallest ordering such that is also lexicographically greater than $$$A$$$.

An ordering $$$P_1, P_2, \dots, P_N$$$ is considered lexicographically smaller than another ordering $$$Q_1, Q_2, \dots, Q_N$$$, if $$$P_i \lt Q_i$$$, for the first $$$i$$$ where $$$P_i$$$ and $$$Q_i$$$ differ.

Given the structure of Byteland and the infection log of Virus A, please help the scientists to predict the order of cities infected by Virus B or print $$$-1$$$ if such ordering does not exist.

In East Hackerland, there is a country called Jakanda which possesses highly advanced technology. It consists of $$$N$$$ cities and $$$N - 1$$$ bidirectional roads. Each road has its own length and connects two cities. It is possible to travel from a city to any other city via these roads.

The Black Panda, king of Jakanda, is facing a problem. Some of the cities are having riot. A city under riot would send out a rebel army and try to capture one other city ("targeted city"). Black Panda is not going to let it happen. He would send a scout from the targeted city to the city under riot. Both the rebel and scout will walk for 1 mile toward their own destination during the day and rest at night. The scout would only spot the rebel army only if they are at the same location and it is at night. If the scout fails to spot the army, the rebel army would capture its target city.

Other than the riot, the length of some of the roads in Jakanda would change due to damage of the war.

Now there are $$$Q$$$ events in chronological order. Each event is one of the two types:

1 $$$u$$$ $$$v$$$, which denote city $$$u$$$ is now under riot and is sending a rebel army to capture city $$$v$$$. Note that city $$$v$$$ might have rebellion or captured before, but in these cases we would consider Black Panda had already suppressed it.

2 $$$i$$$ $$$l$$$, which denote the $$$i^{th}$$$ road is now changed to length $$$l$$$.

For each type 1 event, output JAKANDA FOREVER if the scout could spot the rebels, output WE NEED BLACK PANDA otherwise.

What do kids do when they go dine at a Chinese restaurant ("yum cha")? Back when portable game consoles and smartphones were not available, some kids may opt to play with toothpicks, forming figures on the dining table.

Hand-written digits contain curly strokes, but by using the seven-segment display, digits can be represented neatly using only straight segments. The diagram below shows digits $$$0$$$ to $$$9$$$ in seven-segment display:

Alex wants to form a number between $$$0$$$ and $$$99$$$ (inclusive), by using toothpicks as segments in the seven-segment display (one toothpick per segment, naturally). He insists on forming exactly using two digits, so $$$0$$$ will be written as $$$00$$$, $$$1$$$ will be written as $$$01$$$, and so on.

Assume the tens digit is $$$X$$$ and the ones digit is $$$Y$$$. To use fewer toothpicks, Alex invents a rule for merging $$$X$$$ and $$$Y$$$. First, Alex defines the left part of a digit as the two vertical segments on its left. Similar for right part. Refer to the following diagram.

If the right part of $$$X$$$ and the left part of $$$Y$$$ are the same, then the parts can be merged, allowing a more compact and toothpick-friendly representation. See the following example.

There is one exception to this rule. As you may have noticed, if $$$X = 1$$$, then after merging it will look like one single digit. Therefore, Alex will not merge the two digits if the tens digit $$$X$$$ equals $$$1$$$.

Alex is trying to form $$$T$$$ numbers. For each number, determine the number of toothpicks needed to form the number. Whenever digit-merging is possible, Alex will merge the digits.

Hackerland's Theme Park has an exciting attraction: a labyrinth that can be treated as a $$$3 \times W$$$ grid. It has three special squares: $$$A = (1, a)$$$, $$$B = (3, b)$$$, and $$$X = (2, 1)$$$. Two players will start at $$$A$$$ and $$$B$$$ respectively and will try to reach $$$X$$$ as quickly as possible. In one step, a person can move one square up, down, left, or right. It is possible for both of them to be located at the same square at the same time.

For convenience, let $$$dist(U, V)$$$ denote the distance between squares $$$U$$$ and $$$V$$$, i.e. the number of steps needed to reach $$$V$$$ from $$$U$$$. If $$$V$$$ is not reachable from $$$U$$$, then $$$dist(U, V) = \infty$$$.

You are concerned that the game may be unfair, if $$$dist(A, X) \neq dist(B, X)$$$. Therefore, you are going to place some (possibly zero) obstacles at some of the squares, so that $$$dist(A, X) = dist(B, X) \lt \infty$$$.

Originally, the grid has no obstacles. You cannot add obstacles to squares $$$A$$$, $$$B$$$, and $$$X$$$. Find a way to create a fair labyrinth!