After the first snow this winter, students of Innopolis University built a string of letters out of snow. Unfortunately, over time, some of them have collapsed.
One student plans to rebuild new letters instead of the destroyed ones, but they want their initials (a two-letter string made up of the first letters of his first and last name) to appear as often as possible in the rebuilt string. Only occurrences where the student's initials appear as two consecutive letters count. Help them do it.
The first line contains a string consisting of capital English letters and question marks. Question marks correspond to missing letters. The string length ranges from 1 to $$$10^5$$$ characters.
The second line contains a two-letter string — the student's initials.
In the first line, print the maximum number of times the student's initials can appear in the string after replacing all question marks with letters. In the second line, print the string itself. If there are multiple answers, print any.
| Subtask | Points | Constraints |
| 1 | 60 | Student's initials are two equal letters |
| 2 | 40 | No additional constraints |
I?NO?OLIS?PE? OP
2 INNOPOLISOPEN
???? AA
3 AAAA
NONE GG
0 NONE
Julia is about to move into her new house! There are two flower beds in the garden at the new place, currently containing no flowers. The closest flower shop "Innoflower" sells $$$n$$$ types of flowers selling, enumerated from $$$1$$$ to $$$n$$$.
Julia has already bought all flowers she plans to plant: she bought exactly $$$a_i$$$ flowers of type $$$i$$$. In addition, to make sure the design is diverse, Julia has made an additional restriction: the number of flowers of type $$$i$$$ does not exceed $$$i$$$ (in other words, $$$1 \le a_i \le i$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$).
Julia wants to plant all flowers in her two flower beds in the most beautiful way possible. To keep the harmony, she plans to put all flowers of the same type in one flower bed (that is, all flowers of type $$$i$$$ must be either in the first flower bed or in the second one). At the same time, to ensure maximum symmetry, Julia wants the difference in the number of flowers in flower beds to be as small as possible.
Housewarming party is too soon, so help Julia out and find the required planting of flowers!
First line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of different types of flowers in "Innoflower".
In the second line, there are $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le i$$$) — the number of flowers of each type.
In the first line, print one non-negative integer — the least possible difference of numbers of flowers in flower beds.
In the second line, print the planting of flowers in the following format: $$$n$$$ integers $$$w_1, \ldots, w_n$$$, where $$$w_i = 1$$$ if all flowers of type $$$i$$$ should be planted in the first flower bed, and $$$w_i = 2$$$ otherwise.
If there are more than one possible plantings with the minimum difference, print any of them.
| Subtask | Score | Constraints |
| 1 | 15 | $$$a_i = i$$$ |
| 2 | 20 | $$$n \le 16$$$ |
| 3 | 25 | $$$n \le 100$$$ |
| 4 | 40 | $$$n \le 2 \cdot 10^5$$$ |
5 1 2 1 4 3
1 1 2 1 1 2
2 1 1
0 2 1
In the first example, we have $$$1+1+4=6$$$ flowers in the first flower bed and $$$2+3=5$$$ flowers in the second, so the difference equals $$$1$$$. It is impossible to plant the same number of flowers on two blower beds. Note that there are other optimal plantings.
In the second example, there is one flower on each of the flower beds, so the difference is equal to $$$0$$$.
Consider all divisors of some integer $$$n$$$. Choose some of these divisors, then arrange them in a circle so that the ratio of any two adjacent numbers is a prime number.
Find the maximum number of divisors of $$$n$$$ you can choose, and find the appropriate arrangement.
The first line of input contains the integer $$$n$$$ ($$$2 \le n \le 10^9$$$).
In the first line, print a single integer $$$k$$$ — the maximum number of divisors of $$$n$$$ you can choose.
In the second line, print $$$k$$$ integers — different divisors of $$$n$$$ in the order they appear on the circle. Any two adjacent and the first and last numbers in this list must differ by multiplication by some prime number.
| Subtask | Score | Constraints |
| $$$1$$$ | $$$10$$$ | $$$n \le 10$$$ |
| $$$2$$$ | $$$15$$$ | $$$n \le 50$$$ |
| $$$3$$$ | $$$20$$$ | $$$n \le 150$$$ |
| $$$4$$$ | $$$20$$$ | $$$n = 10^m$$$ for integer $$$m \ge 0$$$ |
| $$$5$$$ | $$$15$$$ | $$$n = 2^x \cdot 3^y \cdot 5^z$$$ for integers $$$x, y, z \ge 0$$$ |
| $$$6$$$ | $$$10$$$ | $$$n$$$ is not a square of an integer |
| $$$7$$$ | $$$10$$$ | No additional constraints |
10
4 1 2 10 5
You probably know that every number has a unique representation in the binary number system. For example, $$$21 = 16 + 4 + 1 = 10101_2$$$.
Let's introduce the concept of the redundant binary number system. In this system, the weights of digits are powers of two, but every digit can be equal to $$$0$$$, $$$1$$$, or $$$2$$$, without leading zeros. This representation has many advantages, but numbers can have multiple representations; for example, there are $$$5$$$ ways to represent $$$21$$$ in the redundant binary number system:
- $$$21 = 16 + 4 + 1 = 10101_2$$$
- $$$21 = 16 + 2 + 2 + 1 = 10021_2$$$
- $$$21 = 8 + 8 + 4 + 1 = 2101_2$$$
- $$$21 = 8 + 8 + 2 + 2 + 1 = \textbf{2021}_2$$$
- $$$21 = 8 + 4 + 4 + 2 + 2 + 1 = 1221_2$$$
Denote the number of ways to represent $$$n \ge 0$$$ as $$$a(n)$$$. We consider $$$0$$$ to have one representation, so that $$$a(0) = 1$$$.
What problem involving $$$a(n)$$$ can we come up with? Calculate $$$a(n)$$$ for a given $$$n$$$? Nah, that's too easy. Solve the "inverse" problem: given $$$x$$$, find $$$n$$$, such that $$$a(n) = x$$$? That's trivial too.
For two given integers $$$x$$$ and $$$y$$$ find the minimum $$$n$$$, such that $$$a(n) = x$$$ and $$$a(n + 1) = y$$$.
The input contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 10^{18}$$$).
If such $$$n$$$ does not exist, print $$$-1$$$. Otherwise, print the minimal required $$$n$$$. Because the answer can be huge, print it modulo $$$999\,999\,001$$$.
| Subtask | Points | Constraints |
| 1 | 15 | $$$x, y \le 6$$$ |
| 2 | 22 | $$$x, y \le 20$$$ |
| 3 | 34 | $$$x, y \le 10^6$$$ |
| 4 | 29 | $$$x, y \le 10^{18}$$$ |
3 1
6
5 7
21
6 2
-1