The 15 puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8 puzzle. If the size is $$$3 \times 3$$$ tiles, the puzzle is called the $$$8$$$ puzzle or $$$9$$$ puzzle, and if $$$4 \times 4$$$ tiles, the puzzle is called the $$$15$$$ puzzle or $$$16$$$ puzzle named, respectively, for the number of tiles and the number of spaces. The goal of the puzzle is to place the tiles in order by making sliding moves that use the empty space.

Here is some pictures for better understanding.

This picture is the final state of the game.

This picture is a condition that you can not solve it.

This picture is a shuffle of game.

So your target is to solve a shuffled 15 puzzle. You can use 'U','D','L','R' to move tiles.

'U' means move the tile under the empty space up to the empty space.

'D' means move the tile above the empty space down to the empty space.

'L' means move the tile on the right side of the empty space left to the empty space.

'R' means move the tile on the left side of the empty space right to the empty space.

Now you can use these letters to represent your solution. But it may not have a solution, just print "No".

SVM loss is a useful loss funtion in machine learning. Assume there are $$$n$$$ training examples and $$$m$$$ classes in a image classification problem. Each training example contains a training image and a label. The label is an integer in range $$$[1,m]$$$.

Our machine learning model takes $$$n$$$ training images as input and outputs $$$n$$$ score vectors of $$$m$$$ dimensions. SVM loss of $$$ith$$$ score vector $$$L_i$$$ is defined as the following formula.

$$$L_i = \sum_{j=1,j \neq label_i}^{m} max(0, S_{i,j}-S_{i,label_i}+Hinge)$$$, where $$$Hinge$$$ is a constant.

We want to accelerate the model training process by calculating the SVM loss function quickly. You need to answer $$$Q$$$ queries asking the sum of SVM loss from $$$lth$$$ score vector to $$$rth$$$ score vector when $$$Hinge$$$ equals $$$h$$$. Formulaly, you need to answer $$$\sum_{i=l}^{r} L_i (Hinge=h)$$$.

lyw and his friend zyw are playing an boring game called Easy Nim. In this game, there is a pile of $$$n$$$ stones on the table. Two players take turns choosing some stones and removing them from the table. The game always starts from lyw and ends when there is no stone left on the table. The player who removes the last stone wins this game.

But they all felt that the rules of the game were a bit boring, so they added some additional constraints. First, the player can only remove at least $$$1$$$ stone and at most $$$m$$$ stones from the table each round. The second, zyw will have $$$k$$$ extra magic cards as a blessing from God. Each card has a number written on it. When zyw uses this magic card, he can change the upper limit of the stone that can be removed in the rest round of the game to it, but he can't remove any stones during the round when he uses the magic card. Note that each card could be used only once.

Support that both of them are witty enough to win the Easy Nim game, please tell Jury who can win this game?

lyw and his friend zyw are playing an exciting game called "Hard Nim". In this game, there is a pile of $$$N$$$ stones on the desk. Two players take turns selecting some stones and remove them from the desk. lyw will always go first. The game ends when there is no stone left on the desk. The player who removes the last stone wins the game.

There are also two additional constraints in the game. First, in each turn, the player must remove at least 1 and at most $$$M$$$ stones from the desk. Second, the player will lose the game if the number of stones remaining(represents in binary) has odd number of ones after his removing.

Assume both of them playing optimally, can you judge who will win the "Hard Nim" game?

Consider an array {$$$a_n$$$}, where $$$a_1$$$=2 and $$$a_n$$$=$$$2^{a_{n-1}}$$$, for all n>=2. As you can imagine, while n is huge enough, $$$a_n$$$ looks like a tower, and we call this tower "Power tower".

But as we all know, computer has difficulty in dealing with big integers, so he defines another array $$$b_n$$$=$$$a_n$$$ It is easy to prove that {$$$b_n$$$} is a convergent array.(In other words, $$${\lim_{n \to+ \infty}}b_n$$$ exists). Your task is to calculate the $$${\lim_{n \to+ \infty}}b_n$$$.

Recently, lzd love play Battlefield 1, he especially likes to play scouts. In the game he is a shooter and can snipe any opponent he sees. But there is an interval feature called damage drop in the game, which means that if the distance between enemy and him is in this interval, lzd only needs to shoot it once to kill it, otherwise he needs an extra shot to make up for the damage. For example, now lzd has a Gewehr 98, and its damage range is $$$[80, 125]$$$, so all enemies whose distence is within this range can be killed with just one shot.

Today, lzd is trapped on the top of the mountain by $$$n$$$ enemies. But he only has a homemade rifle with $$$m$$$ bullets while the rifle's damage drop is $$$[l,r]$$$. You have known all the distance between he and enemies. Please tell him whether he can finish all the kill or not.

In response to the national call for energy conservation and emission reduction, Master Yi, the director of the Transportation Bureau in Pigeon province, decided to demolish some unnecessary roads to reduce waste of resources. There are $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$ in his province. Also there are $$$m$$$ roads connecting the cities. One can go from city $$$u_i$$$ to $$$v_i$$$ (and vise versa) using $$$i$$$-th road, the length of this road is $$$w_i$$$.

Master Yi doesn't want to waste the money of the province, so he is going to close some of the roads in response to the country's call to save resources. Please tell Master Yi the maximum number of the roads which can be closed such that the distance between any two cities in Pigeon province does not change.

In order to collect geographical information on Mount Wolwz, a team of geographical observers needed to establish four observation points on the mountain. In order to obtain accurate data, the four observation points need to be exactly the four vertices of a square when viewed from the air. The observation algorithm used by the team required at least three of the observation points to be at the same height. And for the last observation point, which is at a different height to the other three, it needs to be at a higher position than the other three.

The top view of Mount Wolwz can be seen as a square with $$$n*n$$$ small square platforms, where each piece has an integer height. The group discussed that the higher the three observation points of the same height, the better the result. So they wanted to find out what the highest of the three observation points at the same height was.

There are $$$n$$$ routers in a network each of which has some packets stored in it and a routing table. Routers look up ip address of the packet in its routing table and send the packet to corresponding router neighbor. If the packet's ip address is not in the routing table then the packet will be send to its default router neighbor.

Unfortunately, all of the $$$n$$$ routers have broken down and their routing table become empty. So they can only send packets to their default router neighbor.

There are $$$a_i$$$ packets stored in $$$ith$$$ router at time slot 0. Each of the $$$n$$$ routers send all the packets stored in it to default router neighbor and remove these packets from itself in every time slot. Routers also store the packets it recieved in each time slot.

As a administrator of the network, you want to know how many packets are there in router $$$x$$$ at time $$$t$$$.

People in Kingdom Z loves football. Zyw the king of Kingdom Z wants to establish a football league in his country called Z-league.

There are $$$n$$$ teams in the Z-league and each of them has an unique team name which consists of three uppercase letters. For example, PSG, MCI, MUN are legal team names but FcB, S04, OL are not.

Now, giving you $$$n$$$($$$n$$$ is even) team names. You need to arrange a schedule for the first season of Z-league. Your schedule should meet the following conditions.

1. Each pair of teams, for example team AAA and team BBB should have exactly two matches in the season. One is "AAA vs BBB" in which team AAA plays as the home team, the other is "BBB vs AAA" in which team BBB plays as the home team.

2. Each team has at most one match per week.

3. Number of weeks the season takes should be as little as possible.

Recently, zyw is very interested in number theory. He find a very hard question:

Give a integer $$$n$$$, try to find $$$3$$$ integers $$$x$$$,$$$y$$$,$$$z$$$ satisfied $$$1 \leq x \leq y \leq z$$$ and $$$x+y+z=n$$$ makes the value of $$$gcd(x,y)+gcd(y,z)+gcd(z,x)$$$ as big as possible.

Zyw is a math genius and solved it in just $$$10^{-114514}$$$ second and it costs the judger 1000ms to give answer. Now he wants to know whether there is a faster way to solve it.

Master Yi is a farmer. He has a large farm with many radishes planted in it. Recently, he lost some due to the stealing of wild rabbits. He thus decided to place some fences to protect all his carrots.

The farm is a rectangle consisting of $$$R\times C$$$ cells. Each cell is either empty, contains a carrot, a rabbit or a fence. Rabbits can roam freely around the farm, by repeatedly moving to the left, right, up or down to a neighboring cell. When a rabbit enters a cell with a carrot, it consumes it. However, no rabbit can enter a cell with a fence.

Initially there are no fences. Place fences onto the farm in such a way that no rabbit can reach any carrot, or determine that it is impossible. Note that since you have many fences, you do not need to minimize their number.

Miamiao writes a program and submits it to the judger. The judger tells her the result of each test case by a string containing P or F. P means to pass the test and F means to fail the test. Now Huihui wants to help her debug the program. He can remove the first or the last letter in $$$1$$$ minute or remove any other letter in $$$2$$$ minutes. After removing a letter from the middle the two remaining parts are joined.

Now, Huihui wants to know, how fast can he finish debugging the problem, which means he can obtain a string without any letter F?