The bears have decided to abandon their solitary lives as predators and hunt together. They have formed two groups on the opposite sides of the farm and are preparing to abduct several smaller piglets, whose fate now seems very uncertain.

To prevent their plans from being revealed, the bears will communicate during the operation at a distance using the semaphore alphabet, which they will further encrypt with Caesar's cipher. Caesar's cipher is defined by a single non-negative integer $$$C$$$. Each letter in the message is encrypted by replacing it with the letter that is $$$C$$$ positions further in the alphabet. When the position of the used letter goes beyond the end of the alphabet, counting continues cyclically from the start of the alphabet. So, for example, with $$$C=5$$$, the second-to-last letter in the alphabet is encrypted as the fourth letter in the alphabet. Each letter of the semaphore alphabet is encoded by the position of two lower or upper limbs of a signaling mammal that stands upright, facing the recipient of the message. In the diagram shown below, the center of the diagram represents the torso position of the signaling mammal, and its two limbs are represented by two of the eight possible segments radiating from the center. The assignment between limb positions and letters of the alphabet is provided on a separate page (following the samples).

Now, the bears are going to encrypt their short messages. They are good at semaphore alphabet, but they need some help with Caesar's cipher. Please provide them with this assistance.

There are cows in a 2 by 2 kilometer field. The cows want to have a group meeting, and all of them must attend! It is up to you to plan the meeting to take place as soon as possible.

To model this problem, we approximate each cow as a circle, and for our purposes, there are no collisions - cows can pass through each other freely.

The $$$i$$$-th cow is represented by its initial position $$$\left(x_{i}, y_{i}\right)$$$ and its radius $$$r_{i}$$$, all distances are measured in meters. You can tell each cow to travel in any direction from its initial position at a constant speed from 0 to 1 meter per second. The meeting takes place as soon as all cows occupy the same point in the plane, i.e., there exists a point contained within all circles representing the cows. Find the minimum time in seconds required for the cows to meet.

The farm generates additional income by producing decorated turkey eggs. The farmers, being excessively creative, design various patterns and apply them to the surface of the eggs. The customer orders are handled with the help of specially trained reptile specimen, often it is a Komodo dragon or a member of another suitable reptile species. The reptile had been trained to understand and execute commands in a specific formal language. A customer order is translated into a command for the reptile which then selects a corresponding group of eggs from the production line. The selected eggs are then packed and prepared for shipment.

The command is a regular expression, and the reptile selects such sequence of eggs on the line that exactly matches the given regular expression. The selected sequence does not have to be contiguous, and it does not have to be specified uniquely by the expression. However, the selected sequence always has to be as long as possible, to keep customers satisfied. The reptile recognizes the beginning and the end of the production line, thus the first egg in the selected sequence is not further from the end of the production line than the last egg in the sequence.

Sometimes, the customer's order, and consequently the regular expression, is so demanding that no unempty sequence of eggs can match the expression. In such situation, the reptile is still able to distinguish between two possible scenarios. In the first scenario, an empty sequence containing no eggs can still match the expression. In the second scenario, even an empty sequence of eggs cannot match the expression. In the first scenario, the reptile remains calm, in the second scenario, the reptile gets dangerously annoyed and has to be calmed down.

Check the reptile's operation and, for each given regular expression, determine the maximum possible number of selected eggs in the shipment.

Below is the specification of the regular expressions that control the reptile's activity:

• Each expression is a finite sequence of lowercase letters of the English alphabet, extended with the characters $$$\texttt{?}$$$, $$$\texttt{*}$$$, $$$\texttt{[}$$$, $$$\texttt{]}$$$, $$$\texttt{(}$$$, $$$\texttt{)}$$$.
• Each letter of the English alphabet represents an egg with a specific pattern corresponding to that letter.
• The question mark ($$$\texttt{?}$$$) represents one egg with any pattern.
• The brackets $$$\texttt{[}$$$ and $$$\texttt{]}$$$ are always correctly paired, and inside them, there may be only lowercase letters of the English alphabet, at least one. This pair of brackets and the letters within them always represent a single egg on the line, one whose pattern matches any letter inside the brackets.
• The asterisk ($$$\texttt{*}$$$) replaces any number of repetitions of the sequence immediately preceding the asterisk. This sequence is either a single letter or a question mark or a portion of the expression enclosed in parentheses $$$\texttt{()}$$$ or square brackets $$$\texttt{[]}$$$. The number of repetitions may also be zero.
• Parentheses $$$\texttt{(}$$$ and $$$\texttt{)}$$$ are always correctly paired and are always immediately followed by an asterisk. Inside these parentheses, there is always a regular expression adhering to the rules described above, but it does not contain any parentheses.

A farmer marked a large rectangle on his field using four stakes hammered into the ground at the corners. The rectangle had a non-zero area. His plan was to dig a pond for pike there.

Unfortunately, the next morning, he found out that a new law on the minimum size of the living space for pike was being proposed. He decided to prepare for the new conditions. He pulled the stakes out of the ground and hammered them in at new positions. Because he wanted to use all the already prepared land, he made sure that the previous rectangle was entirely contained within the new, larger one. He was so meticulous, that no point on the boundary of the new rectangle coincided with a point on the boundary of the previous rectangle.

As it often happens, the next morning, he learned that the minimum size of the living space for pike would be even larger than what had been discussed the previous day. So, he repeated the process, pulled the stakes out, and hammered them in at new positions, only to find out the next day that the space needed to be expanded again. This repeated for several days. Finally, when the time to vote came, the proposed law was unanimously rejected. The farmer then decided to return to the original marked area. He pulled out the stakes, thinking he would simply place them back into the holes left by the stakes. However, he suddenly realized that his entire field was now full of holes from all the constant stake-shifting, and he no longer knew which four points represented the original rectangle. To make matters worse, he received a call from the Land Management Office, urgently requesting the area of the land he planned to use for the pond.

We know the coordinates of all the holes left by the stakes. Help the farmer determine the area of the original, smallest rectangle.

There are two fenced areas next to each other: one houses a group of pigs, and the other houses a herd of giraffes. While pigs cannot visit the giraffes, and giraffes cannot visit the pigs, they can communicate over the fence. In fact, they have become such good friends that pigs prefer to talk to giraffes instead of other pigs, and giraffes feel the same way-they would rather talk to pigs than to other giraffes.

This relationship is mutual: if a pig likes to talk to a specific giraffe, that giraffe likes to talk back to that same pig. However, no pig likes to talk to another pig, and no giraffe likes to talk to another giraffe.

If an animal wants to send a message to another animal, even if it doesn't like to talk to it directly, it can do so by passing the message through other animals. Messages can only be passed between animals that like to talk to each other.

To quantify the amount of chatter, we define the noise level between two animals as the minimum number of talks required for a message to be passed from the source animal to the target animal. If a message cannot be passed between two animals, the noise level for that pair is 0 . For instance, if two animals like to talk directly to each other, their noise level is 1 . If the message must pass through one other animal, the noise level is 2 , and so on.

We are interested in the total noise level, which is the sum of noise levels for all unordered pairs of different animals. Note that the noise level between two different animals is only counted once.

The problem is, the number of animals keeps increasing. New animals are born by combining the properties of two existing animals of the same kind, referred to as the parents. The new animal will belong to the same kind as its parents (pig or giraffe). Additionally, the newborn animal can immediately start talking to other animals. The newborn animal likes to talk to exactly the animals that like to talk to exactly one of its parents. Along with the initial setup of animals and their talking preferences, you will be given a sequence of queries describing the birth of new animals. After each animal is born, your task is to calculate the total noise level.

The hamster lives in a rectangular enclosure with floor divided into square fields of the same size, forming a grid. In each field, several larvae are dwelling. The hamster decided to walk around the enclosure, collect the larvae into his bowl, and bring them home for later culinary use. Additionally, he decided to place a trap for common starlings on each field so that they would no longer fly in and steal the larvae. The hamster starts in the northwest corner of the enclosure. From each visited field, he collects the larvae and puts them in the bowl, places a trap on the field, and moves to the next field, which shares a side with the field he is just leaving. The hamster will finish his journey in the southeast corner of the enclosure. But there is a catch, the hamster cannot return to fields he has already visited, otherwise he would get caught in one of his own traps.

We know how many larvae are in each field. Find out the maximum number of larvae the hamster can collect on his journey and avoid all traps.

Aaron, the mink, has two loves: biscuits and prime numbers. Growing up on our farm, he developed a special fondness for both. In the kitchen, he has cookie cutters shaped like the digits 0 through 9 . He fills them with dough, bakes the digits, and arranges them in a row on a tray to form a whole positive number.

Recently, Aaron managed to bake and arrange a prime number. After admiring it, he got hungry and ate one of the digit-biscuits. Without rearranging the remaining digits, he simply shifted them left or right to fill the gap. To his delight, the new number was still prime!

Now, Aaron is curious to see how many prime numbers he can find in a row through this process. Each time, he eats a digit, shifts the remaining ones, and checks if the new number is prime. If leading zeros appear after eating a digit, he happily eats those as well right away. However, if at any point the resulting number is not prime, the process ends immediately.

Today, Aaron baked a new set of digits and formed a new number, not necessarily prime. Aaron's goal is to see the maximum number of prime numbers in a row, starting with the initial number and continuing for as long as possible.

Your task is to compute the maximum possible number of occurrences of prime numbers in this process.

On the outskirts of the town, close to the farm, there stand two parallel power lines, separated by a narrow dirt road. The power lines were a favorite resting spot for a variety of birds.

Today, on this cool autumn morning, the lines are filled with a group of birds. On the first line there are $$$n$$$ consecutive positions for birds numbered $$$0,1, \ldots, n-1$$$. On the second power line there are also $$$n$$$ positions numbered in the same manner.

Initially, every position of the first line is occupied by some birds (possibly zero) and there are no birds on the second power line. Each bird has its desired position to fly to on the second line. No two birds on the same position on the first line share the same desired position.

At one moment, all the birds at once will decide to fly to their desired positions. Every bird flies along the straight line segment connecting its initial and desired position.

It can happen that some pairs of birds crash into each other during their flight. This can happen when their corresponding line segments cross. We shall call such unordered pair of birds dangerous pair.

For example, if a bird on position 2 wants to go to position 1 and the bird on position 1 wants to go to position 2, their paths cross.

The birds will not collide if their paths have the same desired position (on the second line) or if they start from the same position (on the first line). In other words a pair of birds with the same initial or desired positions is not considered a dangerous pair.

The task is very simple. Compute the number of dangerous pairs of birds.

The farmer needs some pork to be packed. This may take several days, so the farmer has allocated $$$N$$$ possible days when the packing can be performed. The whole packing process needs to be completed in a sequence of consecutive days with at least one day. This sequence of days, also called an interval, may not necessarily contain all allocated days.

The farmer has called the bulls and donkeys to help and to do the entire packing job. The bulls and donkeys do not work for free, so the farmer assigned to each day a particular number of cookies he is willing to pay, if the animals work on that day.

The bulls, not being the smartest animals, protested against using such advanced mathematics as summing several numbers of cookies in several consecutive days. They insist on being paid a fixed amount of $$$K$$$ cookies, no matter when or for how long they work.

On the other hand, the donkeys considered the sum to be a too ordinary mathematical operation and required that they are paid the bitwise OR of the numbers of cookies offered for the individual days.

Bitwise OR of two given integers is computed by taking their binary representation and keeping the digit 1 in the result on exactly those positions where at least one of the given two integers has digit 1. For instance, bitwise OR of 9 and 5 is 13.

Furthermore, the bulls and donkeys are willing to work only when they are both paid the exact same total amount. The farmer, finding himself unwilling to deal with the animals any longer, agreed to their conditions and wants to know how many options does he have for scheduling the work. As such, your task is to count the total number of distinct non-empty intervals of days on which the animals are willing to work. Counted intervals may overlap.

Famous magician Leonardo from Pisa is about to visit the farm and amuse the staff with his tricks. There is a long row of rabbit hutches along one wall of the farm yard. Each hutch is permanently occupied by some number of rabbits. To perform his tricks on rabbits, the magician needs to exploit the row of rabbit hutches. However, the farm is planning maintenance, and they can offer the magician only one contiguous segment of the row of the hutches. To help Leonardo, they compiled a list of segments. Leonardo will choose one segment from the list and the hutches outside the segment will be inaccessible to him due to the maintenance.

Before Leonardo chooses a suitable segment, he has to consider his additional restrictions. Each day, Leonardo will perform one trick on the chosen segment. Fundamental part of each trick is a pair of rabbit hutches selected in the segment in such a way that when the total number of rabbits in both hutches is calculated, it is equal to one of the so-called positive Fibonacci numbers. Each day, the calculated Fibonacci number has to be different from all Fibonacci numbers calculated in the previous days, otherwise the principle of magician's tricks could be cracked and publicized. When Leonardo cannot perform more tricks, he has to leave the farm.

Help Leonardo to determine how many days at most he can stay on the farm, for each given segment of rabbit hutches.

The so-called positive Fibonacci numbers form an infinite sequence of integers. It starts with integers 1 and 2, and each next entry in the sequence is the sum of two entries immediately preceding this entry in the sequence.

The sheep are fleeing from the wolf that has entered their pasture. To save themselves, they must escape through fenced paths designated for sheep shearing. The paths are connected to each other and eventually lead to a single exit into the farmyard, where the sheep that escape the wolf will be safe. The paths are arranged in a special formation, consisting of several segments of the same shape, with each segment containing 5 paths. The entry point of each segment, except for the first, is also the exit point of the previous segment.

The entry point of the first segment is in the pasture, and the exit point of the last segment leads into the farmyard. The sheep always run in the same direction along one path, and it never happens that two sheep run along the same path in opposite directions. The sheep cannot jump over the fence of the path. The sheep's escape is further complicated by the fact that halfway along each path there is an automatic gate that allows a certain number of sheep to pass through before closing itself, making the path impassable for other sheep. However, the wolf can jump over the gates on the paths, making him extremely dangerous. We assume (and the sheep assume as well) that the wolf can catch only those sheep which are no longer able to reach the farmyard due to the closed gates.

Determine how many sheep can escape from the wolf at most, given that for each gate it is known how many sheep it will let through.

The diagram shows the paths arranged in a formation of 4 segments.

In a small town called Kocourkov, surrounded by hills and woods, a strange problem has appeared. The town, known for its cozy pubs and friendly people, had always been peaceful until a problem with mice showed up.

But these weren't just any mice. They were smart, quick and seemed to be everywhere at the same time. They had taken over the town's favorite pubs, running through the rafters, nibbling on crumb, and causing a lot of trouble.

In Kocourkov, there are $$$N$$$ places and exactly $$$N-1$$$ roads and it is possible to reach any place from any other place in Kocourkov via the roads. Each road connects a pair of places.

The town council held an emergency meeting in the largest pub U Nacpané Myši. They noticed that the mice are running across the city in a very particular pattern. Each mouse has exactly two lairs scattered across the city and runs only between its two lairs. Each lair is located in one of the places. It has also been observed that the mice are vulnerable about halfway through their usual path. Formally, if mouse's lairs are in places $$$A$$$ and $$$B$$$ then the mouse is vulnerable at place $$$C$$$ if and only if $$$|d(C, A)-d(C, B)| \leq 1$$$ and $$$C$$$ is on the path from $$$A$$$ to $$$B$$$. In this context, $$$d(X, Y)$$$ denotes the distance betwen places $$$X$$$ and $$$Y$$$ measured in the number of roads on a path from $$$X$$$ to $$$Y$$$. Therefore, there may be more than one place where a mouse is vulnerable and a mouse might also be vulnerable in its own lair. After long discussion, the ultimate solution was proposed. The town will place watchcats around the town. A watchcat can get rid of a mouse if the watchcat is on a place where the mouse is vulnerable. One watchcat can get rid of any number of mice. Watchcats are lazy, each of them will always sit on its chosen place, and it will not move away from it.

As purchasing watchcats is not cheap, the town council wants to minimize the amount of watchcats to buy. Help them with this task.