Nick has always struggled with maintaining habits. The problem is that he just can't stop maintaining them. If Nick does something $$$K$$$ times in a row, he has to keep doing it forever.

Luckily, he has started visiting Dr Patternson, an expert in PBT (Pattern Breaking Therapy). The principle of PBT is simple: Nick will visit Dr Patternson every day, and if he has done the same thing $$$K$$$ times in a row on a specific visit, the doctor will charge him money. This will motivate Nick to not continue this habit.

PBT has worked out great for Nick, as he has now successfully quit all his habits. Except for one, the habit of visiting Dr Patternson. The frequent visits are starting to take a toll on Nick's economy, so your task is to calculate how many times he has to pay the doctor for the next $$$N$$$ days.

Formally, let $$$s = s_1s_2s_3\dots s_N$$$ be a string consisting of zeroes and ones. A one means that Nick has to pay the doctor on the $$$i$$$th day. This string is generated one character at a time, in the following way:

1. $$$s_i = 0$$$ if $$$i \leq K$$$.
2. If $$$i \gt K$$$, then $$$s_i = 1$$$ if the previous characters contains a pattern that repeats $$$K$$$ times. More specifically, let $$$s' = s_1s_2\dots s_{i-1}$$$. If there is a nonempty string $$$t$$$ such that the last $$$|t|\cdot K$$$ characters of $$$s'$$$ can be written as $$$t+t+\dots + t$$$, then $$$s_i = 1$$$. Otherwise $$$s_i = 0$$$.

You are given the numbers $$$N$$$ and $$$K$$$, and your task is to calculate the number of ones in the string $$$s$$$.

The picture represents Sample 1. An angry face means that Nick had to pay on the corresponding day.

Erik and his grandpa often go to the forest to pick blueberries. Grandpa always finds the most berries, and even though it is not a competition, Erik has had enough of this. He has observed that grandpa uses a simple greedy strategy to pick as many berries as possible. With this information, Erik will try to finally pick at least as many berries as grandpa.

The blueberry shrubs can be represented as a string $$$s = s_1s_2 \dots s_N$$$ of length $$$N = 10^5$$$, consisting of characters '.' and 'b'. If $$$s_i =$$$ 'b', then there is a berry at position $$$i$$$, otherwise there is no berry there. There will be exactly $$$N/2$$$ berries to start with, and they are distributed uniformly at random.

The berry picking takes place in turns. In one move, a person can choose a position $$$i$$$ ($$$1 \leq i \leq N-3$$$), and pick all the berries at positions $$$i$$$, $$$i+1$$$, $$$i+2$$$, and $$$i+3$$$. Grandpa makes the first move, then Erik makes a move, then grandpa, and so on. Grandpa will always greedily make a move that picks as many berries as possible. Among all such moves, he will pick one uniformly at random.

You are given the string $$$s$$$, and your task is to write a program that decides what moves Erik should make in order to pick at least as many berries as grandpa.

The first line of input contains the number $$$N$$$, the length of the string $$$s$$$. This number will always be equal to $$$10^5$$$, except for in the sample. Your program does not have to solve the sample to get accepted.

The second line contains the string $$$s$$$ of length $$$N$$$. This string has exactly $$$N/2$$$ characters 'b', and their positions are generated uniformly at random.

Then, your program should start interacting with the grader. When it is grandpa's turn, you should read a single integer $$$i$$$ ($$$1 \leq i \leq N-3$$$), meaning that grandpa picks the berries at positions $$$i$$$, $$$i+1$$$, $$$i+2$$$, and $$$i+3$$$. When it is your turn, you should instead print a number $$$i$$$, meaning that you pick the berries at positions $$$i$$$, $$$i+1$$$, $$$i+2$$$, and $$$i+3$$$.

If it is your turn and there are no more berries, your program should terminate without printing anything more. If it is grandpa's turn and there are no berries, then the grader will not make any more moves, and your program should also terminate without printing anything more. If you picked at least as many berries as grandpa, you pass the test case.

Each turn, grandpa greedily makes a move that picks as many berries as possible, and among all such moves, he chooses one uniformly at random.

The strings $$$s$$$ were generated beforehand, so they are the same across different submissions. However, grandpa's behaviour is randomized every submission, so it is possible to get different results if you submit the same code twice.

There will be $$$100$$$ test cases. It is guaranteed that there exists a solution that passes this many cases with very high probability.

The Roman numerals are a numeral system that originated in ancient Rome and was widely used throughout Europe well into the Late Middle Ages. It differs from the Arabic system that we mostly use today in that numbers are written with combinations of letters from the Latin alphabet, where each letter is assigned a fixed integer value. Over the years many different letters were used, which was a cause of frequent confusion. But "modern" style uses only these seven:

A very common misunderstanding of the Roman numerals is that they use a universal subtractive syntax. In a subtractive syntax, a lower digit written before a larger digit will be subtracted from the larger digit. 4 can be written as IIII and IV $$$(5-1)$$$. Romans themselves only really used the subtractive syntax for smaller numbers. For larger numbers, it was largely avoided, to give more clarity. For example, $$$499$$$ can be written LDVLIV, XDIX, VDIV or ID, while older sources most likely would use CDXCIX. Ain't Roman numbers fun?

You are given $$$n$$$ numbers written in the Roman numeral system, and your task is to convert them to the regular Arabic number system.

For the purposes of this problem we will subtract any digit written to the left of a larger digit, even if they are not directly adjacent.

John and Hans are playing a game involving 3 dice. Even though they are all 6-sided, they are not guaranteed to be identical.

First John picks one of the dice and then Hans picks one of the remaining two. Then they both roll their chosen die. If they roll the same number, they both re-roll their die. Otherwise the winner is the one who rolled the highest number.

In case neither John or Hans can win with their chosen dice, they do not bother to re-roll the dice indefinitely and no winner is declared.

Can you help John pick a die that guarantees that he wins with a probability of at least $$$\frac{1}{2}$$$?

Sara is doing her summer internship at NCPC (Never Crashing Personal Computers). One day, a rare creature appeared in the office: an algorithmic problem!

The company has a machine that places electronic components on circuit boards. Normally, it would do this one component at a time. But recently the machine has received an update which allows it to place two different components simultaneously. The bottleneck then becomes the component with greater placement time. Now it is far from obvious what strategy the machine should use in order to minimize the total placement time. Sara decides to write an algorithm to determine this strategy.

You have $$$N$$$ different types of electronic components. There are $$$f_i$$$ copies of the $$$i$$$th type, and the components of this type have a placement time of $$$t_i$$$ nanoseconds. The goal is to place all of the components using a sequence of moves. In one move, the machine can take two components of type $$$i$$$ and $$$j$$$, where $$$i \neq j$$$, and place both of them simultaneously. This takes $$$\max(t_i, t_j)$$$ nanoseconds. The machine can also place a single component of type $$$i$$$ in one move, which takes $$$t_i$$$ nanoseconds.

Calculate the minimum possible time to place all components.

Aivar is very good at number theory. In fact, it is the only thing he is good at, but this doesn't stop him from achieving great things. However, if Aivar wants to solve any problem in life, he first needs to convert it to number theory.

For example, consider a rooted tree with $$$N$$$ vertices. In order to deal with such structures, Aivar first constructs a divisor labelling of the tree. A divisor labelling is a way to label each vertex $$$v$$$ with a positive integer $$$x_v$$$ so that $$$v$$$ is an ancestor of $$$u$$$ if and only if $$$x_v$$$ divides $$$x_u$$$.

After constructing such a labelling, Aivar can simply forget about the tree and just think about the list of numbers $$$x_1, x_2, \dots, x_N$$$.

You are given a rooted tree with $$$N$$$ vertices, and your task is to find a divisor labelling. The vertices are numbered from $$$1$$$ to $$$N$$$, and $$$1$$$ is the root.

A software company resulting from several recent mergers consists of a handful of offices in different cities. At each office there is a HR manager who knows everyone working at that office. Additionally, there are of course a lot of persons in the workforce that know each other, also across the offices. Knowing each other in this context is a symmetric relation, if employee $$$a$$$ knows employee $$$b$$$, then $$$b$$$ also knows $$$a$$$. In comparison, while everyone in the workforce (hopefully) knows of the CEO, that does not mean the CEO knows everyone. In fact, while the CEO does know all the HR managers, she does not know that many other employees. This has got to change!

One of the HR managers is instructed to plan a company outing to let people get to know each other better. Unfortunately, it seems impossible to a find a hotel that can accommodate the whole workforce. Maybe he can turn this into an advantage? He is thinking that by using up to three hotels in the vicinity of each other, perhaps it is possible to divide the employees in three groups, one per hotel, so that no two employees in a group already know each other? That would certainly encourage new acquaintances.

In this early stage in the planning, he doesn't care about the sizes of the groups, but only wants to see if such a division is at all possible. He asks you to help him and provides you with a complete list of pairs of employees who know each other. However, you are not told who the HR managers or CEO are, but you know that the CEO knows at most $$$15$$$ employees (this includes the HR managers) and that the company is distributed over at most $$$8$$$ offices.

Welcome to the world of Heroes of Velmar, the critically acclaimed trading card game developed by Sidney Games! After the tremendous success of the physical card game, Sidney Games has decided to take it to the next level and transform it into an immersive video game experience.

As Sidney Games embarks on this ambitious video game project, they seek the expertise of talented developers like you to bring this digital version to life. The challenge lies in coding the algorithm that determines the winner in the virtual battles that unfold between players. The video game will need to retain the same core mechanics as the original card game, where players compete on three distinct locations over six turns, with abilities and power levels shaping the outcomes.

The full rules of the game are listed below. You are given the state of the locations after Setup and Gameplay have finished and the End of the Game has been reached. Sidney Games has tasked you with implementing the Location Resolution part of the game rules, including the application of Special Abilities, to determine the winner.

The game designers have provided you with images of the cards as well as a JSON file with their specifications.

Heroes of Velmar - Game Rules

Objective

The objective of the two-player card game Heroes of Velmar is to win more locations than the opponent over six turns. If there is a tie, the total power level across all locations acts as a tiebreaker.

Setup

1. Each player selects a deck of cards containing heroes with different abilities and power levels.
2. The players shuffle their decks and draw a starting hand of 7 cards each.
3. Designate three distinct locations for the battle. Each location will have its own separate battlefield.

Gameplay

1. Each player draws 1 card from the deck, to their hand, if possible. Maximum cards per hand is 7.
2. Players take turns playing cards from their hand on any of the three locations.
3. On each turn, players have energy equal to the turn number, for example, on Turn 3, they have 3 energy to spend.
4. Each card has a cost that must be paid using energy to play it on a location.
5. Players can play as many cards as they want as long as the following conditions are met:
   1. They have sufficient energy to spend on the card.
   2. The location has an empty spot. Each player has 4 available spots per location.
6. The power level of each card represents its strength in the game.
7. When the turn ends, the energy not used is lost.

End of the Game

1. The game ends after six turns, at which point locations are resolved, with each location having a winner or a tie.
2. The player who wins the most locations is the overall winner.
3. If the players win an equal number of locations, the total power level across all locations is used as a tiebreaker to determine the winner.
4. If the total power level across all locations is also tied, then the game results in a tie.

Location Resolution

1. Locations are resolved separately at the end of the game.
2. Compare the total power levels of all cards played by each player at the location after applying special abilities.
3. The player with the higher total power level wins the location.
4. If there is a tie, no one wins the location.

Special Abilities

1. Some cards have special abilities that can affect the game. These abilities trigger at the end of the game, before location resolution.
2. Abilities can buff the card's power level, interact with other cards, or manipulate the game state.
3. Two cards that portray the same character are considered to portray distinct characters for the sake of abilities.

The game Heroes of Velmar offers a mix of strategic card play, resource management, and tactical decision-making. Players must choose their heroes wisely, coordinate their plays, and employ their unique abilities to outwit their opponents and emerge victorious in the epic battle for control over Velmar!

Card Explanation:

• Top Left Corner: The energy cost required to play the card on the battlefield.
• Top Right Corner: The power level of the card, representing its strength.
• Text on the Bottom: The name of the card, identifying its character.
• Text Underneath: The card's ability, describing its unique effect during gameplay.

NCPC (Nordic Cargo Plane Control) are testing a new engine for their cargo planes. To this end they have bound a strong and sturdy infinitely thin rope to the centre of their testing platform, and to the engine. We will place a coordinate system onto this testing platform such that the rope is bound at the origin and lays along the positive $$$x$$$-axis to $$$(d, 0)$$$. On this testing platform there are also a number of infinitely thin pillars that can stop the rope, but ignore the engine. As the engine is started it starts rotating the rope counter-clockwise around the origin until it hits a pillar, at which point it is caught and starts rotating around that pillar counter-clockwise instead. The engine is then rotating at a smaller radius as some of the rope is caught between the origin and this pillar. This keeps going until the rope is too short to reach any other pillars.

Running these tests, buying all this infinitely thin rope and setting up these infinitely thin pillars, is expensive. Besides, the workers keep getting these nasty paper-like cuts from all these infinitely thin objects. It would be much more economical to just simulate the behaviour.

A group of scouts are preparing to go to a large meeting with other scouts. Their leader Hildeborg, in spirit of the scout motto "be prepared", wants to distribute some useful items among the scouts that they most probably will need on their adventure. The items come in different sizes, so to make this as fair as possible, she wants to make sure that the total size of items carried by any scout is as small as possible. Furthermore, Hildeborg does not want to give more than two items to any scout as she is afraid that it otherwise will be too hard for them to remember to bring everything. Given the sizes of the items, what is the least maximum total size, computed as the sum of items, any scout will have to carry?

Karl is an aspiring C programmer, and is excited by the risks and rewards of low-level manual memory management. In the program he currently develops, he stores a string containing $$$N$$$ non-zero bytes into a buffer named "buf". By mistake he accidentally made the buffer $$$2 N$$$ bytes in size. The last $$$N$$$ bytes of the buffer consists of only zero-bytes.

Now Karl needs to know the value $$$N$$$, the size of the string, in a separate part of the program. Traditionally you would recover the length of a string using the strlen-function, which reports the position of the first zero-byte in the provided buffer using a linear scan. However, Karl finds that this is much too slow, and that it defeats the advantage of using C in the first place. Can you help Karl efficiently recover $$$N$$$ without crashing his program?

The contents of the buffer in sample interaction 3 are shown here.

This is an interactive problem where interaction proceeds in rounds. In each round your program can attempt to read a byte from the buffer or report the answer (the value of $$$N$$$):

• read: Write a line containing "buf[$$$i$$$]" if you want to try to read byte $$$i$$$ of the buffer. If $$$0 \leq i \lt 2N$$$, then you will get the value of the byte stored in the buffer at index $$$i$$$. If $$$i \lt N$$$ then this will be an integer between $$$1$$$ and $$$255$$$, otherwise it will be $$$0$$$. If $$$i \geq 2 N$$$ or $$$i \lt 0$$$, you will get the response "Segmentation fault (core dumped)" and your program should exit.
• answer: Write a line containing "strlen(buf) = $$$M$$$" if you want to report that you think that $$$N = M$$$. Afterwards your program should exit. Your submission will be accepted if you answered correctly, if you did not trigger a segmentation fault, and if you did not attempt to read entries from the buffer too many times.

A maximum of $$$2 \lceil{\log_2 N\rceil}$$$ reads can be made. If your program attempts to read from the buffer after reaching the limit, it will get the response "Too many reads" and your program should then exit.

It is guaranteed that $$$2 \leq N \leq 10^{18}$$$.