2026-2027 ICPC NERC, Kyrgyzstan Qualification Contest
A. A Bit of History
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Kyrgyzstan has been taking part in ICPC competitions since 1996, when the North-Eastern European Regional Contest (NEERC) was organized.

In the 2003-2004 season, the team from Kyrgyzstan reached the ICPC World Finals for the first time, and in 2005 the first ICPC regional championship was held in Kyrgyzstan.

Since then, the regional championship has been held every year.

In 2019, due to the increase in the number of participants, an additional qualification stage was introduced — but due to COVID restrictions, it was not held in 2020 and 2021.

However, all of this is true for student teams — school teams from Kyrgyzstan that wanted to participate in the VKOSHP finals had to qualify every year through the general online selection.

And now, in 2026, the situation for school teams has finally changed — now, in parallel with the student team championship in Kyrgyzstan, which is a qualifier for the NERC Finals, a school team championship is also held, which is a qualifier for VKOSHP.

As in the case of student teams, school teams first need to pass a qualification stage, and based on its results the best teams will advance to the main stage of the championship.

The author of this problem decided that this event is a good basis for a problem.

For a given year $$$Y$$$, output all team competitions that were held or will be held in Kyrgyzstan in that year.

Input

The only line contains an integer $$$Y$$$ $$$(2005 \le Y \le 2026)$$$ — the year of the competitions.

Output

In the first line, output an integer $$$k$$$ — the number of team competitions held (or to be held) in year $$$Y$$$ in Kyrgyzstan.

In the next $$$k$$$ lines, output one competition per line (in any order):

  • if in year $$$Y$$$ there was/will be a student team championship — output ICPC Regional;
  • if in year $$$Y$$$ there was/will be a qualification for the student championship — output ICPC Qual;
  • if in year $$$Y$$$ there was/will be a school team championship — output School Regional;
  • if in year $$$Y$$$ there was/will be a qualification for the school championship — output School Qual.

The lines may be output in any order.

Examples
Input
2026
Output
4
School Qual
School Regional
ICPC Qual
ICPC Regional
Input
2019
Output
2
ICPC Qual
ICPC Regional
Input
2021
Output
1
ICPC Regional
Input
2007
Output
1
ICPC Regional
Note

In the first example ($$$Y = 2026$$$), for the first time in history, all four competitions are held in the same year at once: the ICPC student championship, its qualification, as well as the newly introduced school championship and its qualification.

In the second example ($$$Y = 2019$$$), this is the first year when, in addition to the ICPC student regional championship, its qualification was also held.

In the third example ($$$Y = 2021$$$), due to COVID restrictions, the qualification stage for the student championship was not held again (as in 2020), so only the ICPC regional championship itself took place.

In the fourth example ($$$Y = 2007$$$), we go back to 2007, when only the ICPC student regional championship was held, without any qualifications.

B. Responsible Laundry
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One of the features of adult life is the proper approach to washing clothes:

  • if you wash a new colored sweater together with white socks — the socks will no longer be quite white;
  • if you wash very dirty trousers together with several T-shirts — then you will have to wash the T-shirts again separately afterward.

Many examples can be invented, but here we will fix several basic rules of a "responsible washer":

  • all socks can be washed together, but separately from all other clothes;
  • for the remaining clothes, the following rule applies:
    • bright clothes — only with the same color;
    • white clothes separately;
    • dark, but not bright, clothes separately;
  • T-shirts can only be washed with T-shirts;
  • an additional rule for sweaters and trousers:
    • they can be washed together with each other;
    • but no more than 2 sweaters and/or trousers in one wash, otherwise they will not be washed properly.

Your wardrobe contains $$$N$$$ clothing items, each described by its color and type.

Determine the minimum number of washes required according to the rules described above.

Input

The first line contains one integer $$$N$$$ $$$(1 \le N \le 10^4)$$$ — the number of clothing items available.

Each of the next $$$N$$$ lines contains the description of one clothing item in the wardrobe: two words separated by a space $$$c_i$$$ $$$t_i$$$ — the color and the type of the clothing item, respectively.

$$$c_i$$$ can be one of the following words:

  • White — white (light color);
  • Black — black (dark color);
  • Yellow — yellow (bright and light color);
  • Red — red (bright and light color);
  • Green — green (bright and dark color);
  • Blue — blue (dark color);
  • Gray — gray (dark color).

$$$t_i$$$ can be one of the following words:

  • Socks — a pair of socks;
  • T-shirt — T-shirt;
  • Hoodie — sweater;
  • Trousers — trousers;
  • Jeans — jeans (also trousers).
Output

Print one integer — the minimum number of washes taking into account all the rules described above.

Examples
Input
10
Red Socks
Black Jeans
White T-shirt
Yellow T-shirt
Red Hoodie
Green Socks
Blue T-shirt
White T-shirt
Blue Hoodie
Gray Trousers
Output
7
Input
8
Yellow T-shirt
Black T-shirt
Red T-shirt
Gray T-shirt
Red T-shirt
Blue T-shirt
Green T-shirt
Blue T-shirt
Output
4
Input
6
Red Socks
Black Socks
Black Socks
White Socks
Blue Socks
White Socks
Output
1
Input
9
Blue Hoodie
Black Jeans
White Trousers
Green Hoodie
Red Hoodie
Blue Jeans
Blue Jeans
White Jeans
White Hoodie
Output
6
Note

Example 1.

  • Both red and green socks can be washed together — one wash for all socks.
  • Two white T-shirts are washed separately from the other T-shirts.
  • The yellow (bright) T-shirt is washed separately.
  • The red (bright) sweater is washed separately.
  • The blue (dark) T-shirt is washed separately from dark sweaters and trousers.
  • The blue sweater, gray trousers, and black jeans can be washed together, but no more than two such items in one wash, so two washes are needed.

In total, there are $$$7$$$ washes: $$$1$$$ for socks, $$$3$$$ for T-shirts, $$$1$$$ for the bright sweater, and $$$2$$$ for the dark sweaters and trousers.

Example 2.

  • Yellow, red, and green T-shirts — three separate washes for three separate bright colors.
  • Black, blue, and gray T-shirts are washed separately (all dark T-shirts together).

In total, there are $$$4$$$ washes: one each for red, yellow, green, and dark T-shirts, regardless of the number of items of each color.

Example 3.

All socks are washed in one wash, regardless of their number and color.

Example 4.

  • White items are washed separately (two washes for three items, since there can be no more than two sweaters and/or trousers in one wash).
  • The green and red sweater are washed separately (two washes, one for each color).
  • Gray, blue, and black trousers and hoodies are washed separately from white and bright items (two washes for four items).

In total, there are $$$6$$$ washes.

C. Sisyphus's Labor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have probably heard the legend of Sisyphus — as punishment for various offenses against the gods, he is forced to push a heavy stone up a mountain.

But when the stone reaches the top — it immediately rolls back down, and Sisyphus is forced to start all over again.

This has been going on for more than one century already — and Hades (the ruler of the underworld) decided to somehow make this action more interesting.

Now Sisyphus is forced to drag the stone along an infinite straight line.

During the day, Sisyphus can drag the stone by at most $$$A$$$ meters to the right (in the positive direction).

But at night, a strong wind starts blowing, which blows Sisyphus together with the stone to the left (in the negative direction).

To make things more interesting, the wind gets stronger every night — on the $$$i$$$-th night, the wind will blow Sisyphus $$$i \cdot B$$$ meters to the left.

Hades is interested in watching Sisyphus as long as he makes at least some progress to the right. Otherwise, Hades changes the parameters $$$A$$$ and $$$B$$$ and starts Sisyphus's punishment from the beginning.

For each pair $$$A$$$ and $$$B$$$, determine the maximum distance to the right Sisyphus can advance.

Input

The first line contains an integer $$$Q$$$ $$$(1 \le Q \le 10^4)$$$ — the number of different punishment variants.

Each of the next $$$Q$$$ lines contains two integers $$$A_i$$$ and $$$B_i$$$ $$$(1 \le A_i, B_i \le 10^9)$$$ separated by a space — the distance Sisyphus can drag the stone to the right in one day, and the initial wind strength for the $$$i$$$-th punishment variant.

Output

Print $$$Q$$$ lines.

In the $$$i$$$-th line, print one integer $$$D_i$$$ — the maximum positive distance Sisyphus can advance in the $$$i$$$-th punishment.

Example
Input
5
10 3
3 10
42 42
12345 876
987654321 1
Output
22
3
42
93195
487730529388812681
Note

The first punishment.

Let us consider Sisyphus's coordinate on the line after each day and night:

  • at the beginning, he is at $$$0$$$;
  • after the first day, he moved to $$$10$$$ meters to the right;
  • after the first night, he was blown $$$3$$$ meters to the left — that is, he ended up at $$$7$$$;
  • after the second day, he advanced to $$$17$$$;
  • after the second night, he was blown $$$2 \cdot 3$$$ meters to the left — now he is at $$$11$$$;
  • after the third day, he dragged the stone to $$$21$$$;
  • after the third night, the wind pulled him $$$3 \cdot 3$$$ meters — and Sisyphus ended up at $$$12$$$;
  • after the fourth day, Sisyphus reached $$$22$$$;
  • after the fourth night, the wind moved Sisyphus by $$$4 \cdot 3$$$ meters — to $$$10$$$;
  • after the fifth day, Sisyphus managed to reach $$$20$$$;
  • after the fifth night, Sisyphus was blown $$$5 \cdot 3$$$ meters — to $$$5$$$.

It can be seen that Sisyphus advanced maximally to $$$22$$$ — after that, the wind will keep pushing him further and further to the left.

The second punishment.

  • during the day, Sisyphus moved $$$3$$$ meters to the right;
  • during the night, Sisyphus was pulled $$$10$$$ meters to the left — to coordinate $$$-7$$$.

Hades realized that he had overcomplicated things — and ended this trial.

The third punishment.

  • on the first day, Sisyphus moved as much as $$$42$$$ meters;
  • on the first night, the wind pulled Sisyphus back to $$$0$$$;
  • on the second day, Sisyphus again reached $$$42$$$ meters;
  • on the second night, the wind had already pulled Sisyphus by $$$2 \cdot 42$$$ meters — to the mark $$$-42$$$.

It was pointless to continue any further.

The fourth punishment.

This example is intended for additional verification of the correctness of your calculations.

The fifth punishment.

This example is intended for additional verification of the efficiency of your calculations.

D. Chatbot on a Calculator
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Did you know that in the past, even calculators were programmed in computer science classes?

The author of this problem personally learned about this from their parents, who did something similar in the late 1980s.

In 2026, the main trend is communicating with various LLM models in chat mode (and not only that).

But is it possible to communicate in a similar way with a chatbot programmed on a calculator?

It is possible if we consider some digits to be similar to letters of the Latin alphabet:

  • digit 0 is similar to O;
  • digit 1 is similar to I;
  • digit 5 is similar to S;
  • digit 8 is similar to B.

And if you turn the calculator upside down, you can see two more correspondences:

  • digit 3 is similar to an upside-down E;
  • digit 7 is similar to an upside-down L.

We will call a number $$$X$$$ a "word" if all of its digits are similar to letters:

  • number 8015 looks like the word "BOIS";
  • number 5337 does not look like a word, but when turned upside down it looks like "LEES";
  • number 123 does not look like a word, since digit 2 is not similar to any letter;
  • number 0158 is not a valid number, since it starts with a leading zero.

Your task is to determine the number of word-like numbers in the interval $$$[0; N]$$$.

Input

The only line contains one integer $$$N$$$ $$$(0 \le N \le 123456)$$$ — the upper bound of the interval $$$[0; N]$$$.

Output

Print two integers $$$C_1$$$ and $$$C_2$$$ separated by a space:

  • $$$C_1$$$ — the number of numbers in the interval $$$[0; N]$$$ that look like a word in the normal orientation;
  • $$$C_2$$$ — the number of numbers in the interval $$$[0; N]$$$ that look like a word in the turned upside down orientation.
Examples
Input
34
Output
8 15
Input
8051
Output
202 1100
Input
123456
Output
1536 10368
Note

Example 1.

In the normal orientation, the following numbers look like words:

  • $$$0, 1, 5, 8$$$;
  • $$$10, 11, 15, 18$$$.
There are $$$8$$$ such numbers in the interval $$$[0; 34]$$$.

In the turned upside down orientation, the following numbers look like words:

  • $$$0, 1, 3, 5, 7, 8$$$;
  • $$$10, 11, 13, 15, 17, 18$$$;
  • $$$30, 31, 33$$$.
There are $$$15$$$ such numbers in the interval $$$[0; 34]$$$.

Example 2.

This test is an additional opportunity to check that your counting is performed correctly.

Example 3.

This test checks that your counting is performed efficiently enough (the bound $$$N$$$ takes its maximum possible value).

Statement is not available in English language
F. What Did I Do This Summer?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Autumn has come — which means everyone starts thinking about how quickly summer flew by...

It seems that a lot happened over these three months — but at the same time, it feels like there could have been even more.

This time you prepared thoroughly — and documented all your activities, dividing them into four categories:

  • sleep;
  • study / work;
  • time on the road;
  • entertainment.

You are interested in the total time spent on each of the four categories of activities.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — the number of records in the log.

Each of the next $$$N$$$ lines contains one log record in the format $$$D$$$ $$$A$$$ (two strings separated by a space), where:

  • $$$D$$$ — the date and time of the start of an activity in the format MM.DD hh:mm:ss — month, day, hour, minute, and second;
  • $$$A$$$ — the type of the activity that started, one of the characters:
    • S — sleep;
    • W — study / work;
    • T — time on the road;
    • R — entertainment.

It is guaranteed that:

  • the records are in strictly increasing chronological order;
  • the first record always contains the date and time 06.01 00:00:00 — the beginning of summer;
  • the date and time of each record are within the interval from 06.01 00:00:00 to 08.31 23:59:59 inclusive.

Note — consecutive records may contain the same activities.

Output

Output $$$4$$$ lines, each containing the total time spent on the corresponding activity type.

The order of the output lines is S, W, T, R (sleep; study / work; time on the road; entertainment, respectively).

Each line must be printed in the format DD hh:mm:ss — the number of days, hours, minutes, and seconds spent on that activity type over the whole summer.

Assume that summer ends exactly at 09.01 00:00:00 (that is, the last activity in the log continues until that moment).

Examples
Input
10
06.01 00:00:00 S
06.01 09:12:34 W
06.02 00:59:47 S
06.02 08:00:00 W
07.16 07:45:00 T
07.16 12:58:27 R
08.01 20:21:53 R
08.25 18:00:07 T
08.25 23:57:59 S
08.26 08:00:00 W
Output
S 1 00:14:48
W 50 07:32:13
T 0 11:11:19
R 40 05:01:40
Input
2
06.01 00:00:00 T
08.29 09:12:34 W
Output
S 0 00:00:00
W 2 14:47:26
T 89 09:12:34
R 0 00:00:00
Note

Example 1.

Let us consider the given log step by step:

  • at the beginning of summer, at midnight on June 1, you recorded that you were going to sleep;
  • on the same day you woke up at 09:12:34 and got to work;
  • you went to sleep again almost at 1 a.m. on June 2;
  • on June 2 you got up at 08:00:00 by alarm and went to work;
  • for a month and a half you forgot to fill in the log — that is, according to the log, you were working all that time;
  • finally, on July 16 you went on a trip — and recorded the start of the trip in your log;
  • on the same day at 12:58:27 you started having fun, also noting this in the log;
  • you remembered the log again only on August 1 — and again recorded the start of entertainment;
  • according to the log, you were having fun until the return trip on August 25 at 18:00:07;
  • after arriving home late in the evening, you immediately fell asleep (not forgetting to record the start of sleep in the log);
  • the next day you got up by alarm at 08:00:00 and went to work;
  • there were no more records, so you were working until the beginning of autumn — September 1 at 00:00:00.

Example 2.

Let us consider the given log step by step:

  • at the beginning of summer, at midnight on June 1, you were traveling somewhere;
  • after that, you forgot about the log for almost the whole summer;
  • you remembered it on August 29 — and recorded that you started working at 09:12:34.

Note that although there are no records of type S and R in the log — you still need to output the total time for them as well (in this case it will be zero, that is, 00 00:00:00).

G. Uniform Change
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A cashier has an infinite number of banknotes with denominations $$$1, 2, \ldots, K$$$.

The cashier prefers the stacks of banknotes to end uniformly:

  • Suppose the cashier gives change as $$$C_1$$$ banknotes of denomination $$$1$$$, $$$C_2$$$ banknotes of denomination $$$2$$$, ..., $$$C_K$$$ banknotes of denomination $$$K$$$.
  • The cashier wants the maximum value among $$$C_1, C_2, \ldots, C_K$$$ to be as small as possible.

Help the cashier — find any way to give $$$N$$$ units of change uniformly.

Input

The only line contains two integers $$$N$$$ and $$$K$$$ separated by a space ($$$1 \le N \le 10^{18}$$$; $$$1 \le K \le 2 \cdot 10^5$$$) — the amount of change and the number of different available denominations.

Output

Print $$$K$$$ integers $$$C_1, C_2, \ldots, C_K$$$ ($$$0 \le C_i \le N$$$) separated by spaces — the number of banknotes of denomination $$$i$$$ in a uniform change of $$$N$$$.

The answer must satisfy the following conditions:

  • $$$\sum_{i=1}^{K} C_i \cdot i = N$$$ — exactly $$$N$$$ units of change are given;
  • $$$\max(C_1, C_2, \ldots, C_K)$$$ is minimal among all ways to give change of size $$$N$$$ using denominations from $$$1$$$ to $$$K$$$.

If there are multiple answers satisfying the conditions, print any of them.

Examples
Input
10 3
Output
2 1 2
Input
61 7
Output
1 3 3 3 3 3 0
Note

In the first example, the cashier gave:

  • $$$C_1 = 2$$$ banknotes of denomination $$$1$$$;
  • $$$C_2 = 1$$$ banknote of denomination $$$2$$$;
  • $$$C_3 = 2$$$ banknotes of denomination $$$3$$$.

In total, the cashier gave $$$C_1 \cdot 1 + C_2 \cdot 2 + C_3 \cdot 3 = 10$$$ units.

In the second example, the cashier gave:

  • $$$1$$$ banknote of denomination $$$1$$$;
  • $$$3$$$ banknotes each of denominations $$$2, 3, 4, 5, 6$$$;
  • $$$0$$$ banknotes of denomination $$$7$$$.

In total, the cashier gave $$$1 \cdot 1 + 3 \cdot (2 + 3 + 4 + 5 + 6) + 0 \cdot 7 = 61$$$ units.

Note that this is only one possible answer with $$$\max(C_1, \ldots, C_7) = 3$$$. It can be shown that there is no answer where $$$\max(C_1, \ldots, C_7)$$$ is less than $$$3$$$.

H. Median for Every Prefix!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$P$$$ of length $$$N$$$.

For each prefix of this permutation, you need to compute its median.

Input

The first line contains one integer $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ — the length of the permutation.

The second line contains $$$N$$$ integers $$$P_1, P_2, \ldots, P_N$$$ $$$(1 \le P_i \le N)$$$ separated by spaces — the elements of the permutation.

It is guaranteed that all values $$$P_i$$$ are distinct.

Output

Print $$$N$$$ integers $$$M_1, M_2, \ldots, M_N$$$ separated by spaces, where $$$M_i$$$ is the doubled median of the elements $$$P_1, \ldots, P_i$$$ (that is, the median of the first $$$i$$$ elements of the permutation multiplied by $$$2$$$).

Example
Input
7
5 2 1 4 7 6 3
Output
10 7 4 6 8 9 8
Note

The median of a set of $$$k$$$ numbers sorted in nondecreasing order as $$$a_1 \le a_2 \le \ldots \le a_k$$$ is defined as:

  • if $$$k$$$ is odd — the value $$$a_{(k+1)/2}$$$;
  • if $$$k$$$ is even — the arithmetic mean of the values $$$a_{k/2}$$$ and $$$a_{k/2+1}$$$, that is, $$$\dfrac{a_{k/2} + a_{k/2+1}}{2}$$$.

Since the median for even $$$k$$$ may not be an integer, you should output its doubled value — it is always an integer.

Let us consider the first example step by step. At each step $$$i$$$, we consider the prefix of the first $$$i$$$ elements of the permutation sorted in nondecreasing order, and compute its doubled median $$$M_i$$$:

  • $$$i = 1$$$: sorted prefix — $$$[5]$$$, the median is $$$5$$$, $$$M_1 = 2 \cdot 5 = 10$$$.
  • $$$i = 2$$$: sorted prefix — $$$[2, 5]$$$, the median is $$$(2+5)/2$$$, $$$M_2 = 2 + 5 = 7$$$.
  • $$$i = 3$$$: sorted prefix — $$$[1, 2, 5]$$$, the median is $$$2$$$, $$$M_3 = 2 \cdot 2 = 4$$$.
  • $$$i = 4$$$: sorted prefix — $$$[1, 2, 4, 5]$$$, the median is $$$(2+4)/2$$$, $$$M_4 = 2 + 4 = 6$$$.
  • $$$i = 5$$$: sorted prefix — $$$[1, 2, 4, 5, 7]$$$, the median is $$$4$$$, $$$M_5 = 2 \cdot 4 = 8$$$.
  • $$$i = 6$$$: sorted prefix — $$$[1, 2, 4, 5, 6, 7]$$$, the median is $$$(4+5)/2$$$, $$$M_6 = 4 + 5 = 9$$$.
  • $$$i = 7$$$: sorted prefix — $$$[1, 2, 3, 4, 5, 6, 7]$$$, the median is $$$4$$$, $$$M_7 = 2 \cdot 4 = 8$$$.