You are given an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Is it possible to turn the array into an arithmetic progression by removing at most $$$k$$$ elements? If it is, then you are also required to minimize the number of element removals.
Recall that a sequence of numbers is called an arithmetic progression if the difference between any two neighboring elements of the sequence is the same, regardless of their choice.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 200\,000$$$, $$$0 \le k \le \min\{\frac{n}{2} - 1, 500\}$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$): the elements of the array.
If it is not possible to turn the array into an arithmetic progression by removing at most $$$k$$$ elements, print $$$-1$$$ on a single line.
Otherwise, in the first line, print an integer $$$m$$$ ($$$0 \le m \le k$$$): the minimum possible number of removed elements. In the second line, print $$$m$$$ distinct integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le n$$$): the indices of the removed elements.
If there are multiple optimal solutions, print any of them.
7 22 4 6 7 8 9 10
2 4 6
5 11 2 3 5 6
-1
You are given an array that initially consists of bytes (that is, integers between $$$0$$$ and $$$255$$$, inclusive). Let us define an occurrence of a pair of numbers $$$(l, r)$$$ in the array as a pair of indices $$$(i, i + 1)$$$ such that $$$a_i = l$$$ and $$$a_{i + 1} = r$$$.
You are to perform the following encoding process on this array:
- Pick a pair of distinct numbers $$$(l, r)$$$ that has the most occurrences in the current array. If there are several such pairs, choose the one with the smallest $$$l$$$; among those, select the one with the smallest $$$r$$$.
- Suppose $$$(l, r)$$$ has $$$q$$$ occurrences. If $$$q \lt 2$$$, stop the process. Otherwise, perform a bulk erasure operation as follows:
For all $$$q$$$ occurrences of $$$(l, r)$$$ simultaneously, erase the numbers in them and write the number $$$255 + i$$$ in the place where the occurrence was located, if this erasure operation is the $$$i$$$-th ($$$i \ge 1$$$). The length of the array will decrease by $$$q$$$.
- If the bulk erasure operation has already occurred $$$k$$$ times, stop the process. Otherwise, go to step 1.
After the process ends, report the erasure operations you have performed, as well as the final array.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50\,000$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100\,000$$$, $$$1 \le k \le n$$$): the initial array size and the maximum number of process iterations.
The second line contains $$$n$$$ integers between $$$0$$$ and $$$255$$$: the elements of the initial array.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100\,000$$$.
For each test case, in the first line, print an integer $$$e$$$ ($$$0 \le e \le \min\{k, n - 1\}$$$): the number of bulk erasure operations performed.
In the $$$i$$$-th of the next $$$e$$$ lines, print three integers $$$l$$$, $$$r$$$, $$$q$$$ ($$$0 \le l, r \le 254 + i$$$, $$$l \ne r$$$, $$$2 \le q \le n - 1$$$), denoting that the $$$i$$$-th bulk erasure operation was performed on a pair of numbers $$$(l, r)$$$, erasing it $$$q$$$ times.
The last line must contain the final $$$n - \sum q$$$ elements of the array. Every element must be an integer between $$$0$$$ and $$$255 + e$$$.
27 71 2 1 3 1 2 14 116 10 20 24
2 1 2 2 256 1 2 257 3 257 0 16 10 20 24
Professor Claudio teaches programming at your university.
Today's lecture topic is attention. Clearly, attention is very important in programming: if you put just one or two extra characters into your program, it might crash!
However, for you, a grandmaster on Coffeeforces, the whole thing is absolutely boring. Sitting, doing nothing, and listening to things you already know certainly wasn't in your plans. It would definitely be better to solve another contest with your team to prepare for the regional competition instead... Other students, despite not being grandmasters, seem to agree with you.
When Claudio opened another slide of his presentation, it was dedicated to the importance of not confusing C++ language operators, referring in particular to the following common incorrect representation of the number $$$a^{b}$$$:
unsigned int a, b;
std::cin » a » b;
unsigned int x = a ^ b;
Your patience was wearing thin: "Professor, everyone knows that this is equal to the bitwise exclusive OR, more commonly known as XOR, of two numbers, and not the power of them. Can you please give us something more interesting?"
"Sure, {username}, I'm aware that you know this, but there are certain things I have to teach anyway," responded the professor. "I have a related problem for you to solve, though. Write a program that, given an unsigned 32-bit integer $$$a$$$, produces all unsigned 32-bit integers $$$b$$$ such that the power $$$a^b$$$ and the bitwise exclusive OR $$$a \oplus b$$$ are the same modulo $$$2^{32}$$$. This also means their unsigned 32-bit integer representations are the same, and you'll help us find when the code from my presentation is correct."
For the purposes of this problem, please consider that $$$0^0$$$ is equal to $$$1$$$, as if you were calculating powers of a number by multiplying $$$1$$$ with that number multiple times.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100\,000$$$). The description of the test cases follows.
The only line of each test case contains a single integer $$$a$$$ ($$$0 \le a \le 2^{32} - 1$$$): the value given by professor Claudio.
For each test case, print one line. First, print the number $$$k$$$ of different suitable values of $$$b$$$ (that is, for which $$$a^b - (a \oplus b)$$$ is divisible by $$$2^{32}$$$). Next, if $$$k \gt 0$$$, print all the different values on the same line in ascending order. The values should be integers between $$$0$$$ and $$$2^{32} - 1$$$.
262147483649
0 1 2147483648
You are given $$$n - 1$$$ points $$$P_i = (x_i, y_i)$$$ on a 2D plane, some of which may coincide. Let the distance between two points $$$P_i$$$ and $$$P_j$$$ be defined as follows:
$$$$$$d(i, j) = \max(|x_i - x_j|, |y_i - y_j|).$$$$$$
Add a new point $$$(x_n, y_n)$$$ with integer coordinates in such a way that the median of the multiset $$$\{d(i, j)~|~1 \le i \lt j \le n\}$$$ will equal a given value $$$k$$$, or state that it is impossible to do so. The added point is allowed to coincide with previously existing points.
Recall that for a multiset containing an odd number $$$q$$$ of elements, its median can be obtained as follows: write down all the elements of the multiset in the sorted order, then take the $$$\left(\frac{q + 1}{2}\right)$$$-th element from that order.
The first line contains an integer $$$n$$$ ($$$2 \le n \lt 2 \cdot 10^5$$$): the number of points after your addition. It is guaranteed that $$$\frac{n(n-1)}{2}$$$ is odd.
The second line contains an integer $$$k$$$ ($$$1 \le k \le 5 \cdot 10^5$$$): the desired median distance.
The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 5 \cdot 10^5$$$): the coordinates of the $$$i$$$-th previously existing point.
If it is possible to add a point with integer coordinates $$$(x_n, y_n)$$$, such that $$$0 \le x_n, y_n \le 10^6$$$ and the median of the multiset of all distances becomes equal to $$$k$$$, print the coordinates of any such point.
Otherwise, print a single integer $$$-1$$$.
340 37 0
4 3
61000 1000010000 010000 100000 05000 5000
-1
Petya wants to visit the only museum in his city.
The museum contains $$$n$$$ rooms connected by $$$n - 1$$$ corridors, with the entrance located in room number $$$1$$$. It is possible to reach any other room from there by moving through the corridors.
Since Petya likes to plan everything in advance, he wants to plan his route through the museum. He will start in room number $$$1$$$, and each time he passes through a corridor, he will study exactly one exhibit in the room he arrives at. Petya doesn't want to waste time, so he wants to finish his path back in room $$$1$$$ without studying the same exhibit twice. Additionally, he won't start studying exhibits until he has moved through at least one corridor.
Help Petya create a route that allows him to study all the exhibits, or tell him that it is impossible.
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$): the number of rooms in the museum.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$): the number of exhibits in the first, second, $$$\ldots$$$, and last room of the museum.
The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), indicating that museum rooms $$$u_i$$$ and $$$v_i$$$ are directly connected by a corridor.
It is guaranteed that the total number of exhibits is at most $$$2 \cdot 10^5$$$. It is guaranteed that all rooms are reachable from room $$$1$$$ using only the described corridors.
If it is possible to create a route that allows Petya to study all the exhibits, output $$$1 + \sum_{i = 1}^{n}{a_i}$$$ numbers: the order of visiting the museum rooms, starting and ending in room number $$$1$$$. Otherwise, if it is not possible, output a single integer $$$0$$$.
If there are multiple solutions, print any of them.
41 1 2 41 42 43 4
1 4 2 4 3 4 3 4 1
23 61 2
0
One of the problems in your "Advanced Geometry, Algebra, and Programming" book is as follows. You are given $$$n$$$ points $$$C_1, C_2, \ldots, C_n$$$ on a plane ($$$C_i \ne C_{i + 1}$$$ for any $$$i$$$). There is also another point $$$D$$$, which is different from all points $$$C_i$$$. You are to draw $$$n$$$ circles $$$\omega_1, \omega_2, \ldots, \omega_n$$$, and also $$$n - 1$$$ tangents $$$l_1, l_2, \ldots, l_{n - 1}$$$ to them, ensuring that all of the following conditions are satisfied:
- for all $$$i$$$ from $$$1$$$ to $$$n$$$, the center of circle $$$\omega_i$$$ is point $$$C_i$$$;
- for all $$$i$$$ from $$$1$$$ to $$$n - 1$$$, line $$$l_i$$$ passes through point $$$D$$$ and is tangent to both circles $$$\omega_i$$$ and $$$\omega_{i + 1}$$$;
- for all $$$i$$$ from $$$1$$$ to $$$n - 2$$$, if circle $$$\omega_{i + 1}$$$ does not pass through $$$D$$$, then lines $$$l_i$$$ and $$$l_{i + 1}$$$ do not coincide;
- the total area of all circles should be maximized. (Note that this is not the same as the area of the circles' union.)
Sadly, none of your friends can help you, as they can solve the problem only if the last of the four conditions is absent, in which case the problem becomes fairly easy. Since the book also covers Programming, it does not provide all the input points on paper, so you have to generate some of them yourself...
The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$). The description of the test cases follows.
The first line of each test case contains four integers $$$n$$$, $$$k$$$, $$$x_D$$$, $$$y_D$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n$$$): the number of circles, the number of point descriptions, and the coordinates of point $$$D$$$. Each of the next $$$k$$$ lines contains two integers $$$p$$$ and $$$q$$$ ($$$-n \le p \lt 2^{16}$$$, $$$0 \le q \lt 2^{16}$$$). If $$$p \ge 0$$$, these denote the coordinates of the next point $$$(p, q)$$$. If $$$p \lt 0$$$, you need to generate the next $$$|p|$$$ points as follows:
Let $$$f(x, y) = 2^{16}x + y$$$ and $$$T(x, y) = ((x \oplus \lfloor x \cdot 2^y\rfloor) + q) \bmod 2^{32}$$$. When generating $$$C_i$$$, we can obtain $$$f(C_i)$$$ as $$$(T(T(T(T(f(C_{i - 1}), 16), -11), 20), -24) \cdot 161120241) \bmod 2^{32}$$$, where $$$\oplus$$$ denotes the bitwise XOR operation, represented as ^ in many programming languages. If $$$i = 1$$$, use $$$C_0 = (0, 0)$$$ in this formula.
It is guaranteed that within any single test case, there are exactly $$$n + 1$$$ points, including the generated points and point $$$D$$$. All points satisfy $$$0 \le x, y \lt 2^{16}$$$, and for any $$$i = 1, 2, \ldots, n - 1$$$, it holds that $$$C_i \ne C_{i + 1}$$$. The sums of $$$n$$$ and $$$k$$$ across all test cases do not exceed $$$3 \cdot 10^6$$$ and $$$3 \cdot 10^4$$$, respectively.
For each test case, print one real number: the greatest possible total area of the circles. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$.
23 3 0 02 02 20 22 1 51614 52212-2 20449
42.904272981 45769.863370150
In the first test case, the radii of the optimal circles are approximately equal to 1.8478, 2.6131, and 1.8478.
In the second test case, the input points are $$$(51502, 52167)$$$ and $$$(51569, 52324)$$$.
For a sequence $$$b$$$ consisting of an even number of positive integers, let us call an integer $$$x$$$ its radius if there exists an integer $$$i$$$ such that the sum of the $$$i$$$-th leftmost and the $$$i$$$-th rightmost elements of $$$b$$$ is equal to $$$x$$$. For example, the sequence $$$(16, 11, 20, 24)$$$ has two distinct radii: $$$31$$$ and $$$40$$$.
Define the gorgeousness of a sequence of even length as the greatest common divisor of all its radii. For example, for the sequence above, it is equal to $$$1$$$.
A sequence $$$b$$$ is a subsegment of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deleting several (possibly zero or all) elements from the beginning and several (possibly zero or all) elements from the end.
You are given a sequence $$$a$$$ of $$$n$$$ integers. Find the sum of the gorgeousness values over all its nonempty subsegments of even length.
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$): the length of the sequence.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$): the elements of the sequence.
Print a single integer: the desired sum.
51 2 3 4 5
36
In the example test case, there are four subsegments of length $$$2$$$. They have gorgeousness values of $$$3$$$, $$$5$$$, $$$7$$$, and $$$9$$$, from left to right.
There are two subsegments of length $$$4$$$ (containing all the elements except $$$1$$$ or $$$5$$$). The subsegment containing $$$1$$$ has a gorgeousness of $$$5$$$, while the subsegment containing $$$5$$$ has a gorgeousness of $$$7$$$.
Therefore, the answer is $$$(3+5+7+9)+(5+7) = 36$$$.
Your team has just completed on-site registration for the ICPC Belarus Regional Contest. While waiting for the opening ceremony, you watch the long queue of teams at the registration point. All these teams will go through the same procedure as you:
$$$\quad$$$ – What is the name of your team?
$$$\quad$$$ – Our name is (here the team representative says the team name).
However, nowadays some team names contain so many special characters and foreign words that even for an experienced organizer, it can be difficult to distinguish between several teams...
$$$\quad$$$ – My apologies, I did not understand. What is your team name?
$$$\quad$$$ – We are team (here the team representative says the team name again).
And sometimes it's not only a complicated team name, but everyone around is talking loudly too...
$$$\quad$$$ – I am really sorry. Could you please repeat it once again?
$$$\quad$$$ – WE ARE TEAM (here the representative says the team name once again, visibly irritated)!!!
$$$\quad$$$ – Oh, now I see. Here are your badges. Good luck!
The last team in the queue is made up of three friends of yours, and coincidentally, they picked a very funny name for their team. You already know what they will say... Reproduce the dialogue for them.
The only line contains a string of $$$1$$$ to $$$100$$$ printable ASCII characters with codes between 32 and 126: the name of your friends' team. It is guaranteed that the name does not start or end with a space.
Print the expected dialogue for the team at registration. You must capitalize every lowercase Latin letter in its sixth line to ensure the text conveys the expressiveness of the team representative.
More precisely, each lowercase Latin letter (a–z, decimal ASCII codes 97 to 122) in the sixth line must be replaced with its corresponding uppercase Latin letter (A–Z, codes 65 to 90), while other characters must remain intact. Refer to the example output for details.
At the end of each line, a newline character must be printed. Make sure that you do not print any extra lines or characters, including whitespace characters.
Department of Graph Efficiency (DOGE) **2025**
What is the name of your team? Our name is Department of Graph Efficiency (DOGE) **2025**. My apologies, I did not understand. What is your team name? We are team Department of Graph Efficiency (DOGE) **2025**. I am really sorry. Could you please repeat it once again? WE ARE TEAM DEPARTMENT OF GRAPH EFFICIENCY (DOGE) **2025**!!! Oh, now I see. Here are your badges. Good luck!
The Emperor of Byteland loves to stroll through the inner courtyard of his palace on summer evenings. However, he recently grew tired of the usual sights and came up with a brilliant idea: to instruct his courtiers to paint the grass! To make the result fascinating, he devised intricate rules for selecting the area of grass to be painted.
The inner courtyard is a rectangle measuring $$$n \times m$$$ meters, divided into $$$1 \times 1$$$ meter squares. Two random points are chosen inside this rectangle, after which the rectangle with opposite corners at the given points and sides parallel to the sides of the courtyard is designated for painting the grass.
Each of the two points is selected according to the following procedure. Each $$$1 \times 1$$$ meter square located in the $$$i$$$-th row and $$$j$$$-th column is assigned a weight $$$p_{i,j}$$$. Let $$$P = \sum_{i=1}^{n}{\sum_{j=1}^{m}{p_{i,j}}}$$$. First, one of the squares is chosen with a probability of $$$\frac{p_{i,j}}{P}$$$. Then, the point is chosen uniformly at random within the selected square.
The Emperor enjoyed this event so much that he issued a decree for it to be held weekly. To estimate the costs to the treasury, you, as the court accountant, have been tasked with finding the expected value of the area of painted grass.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1500$$$): the number of rows and the number of columns of the courtyard.
The $$$i$$$-th of the following $$$n$$$ lines contains $$$m$$$ integers $$$p_{i,1}, p_{i,2}, \ldots, p_{i,m}$$$ ($$$0 \le p_{i,j} \le 250$$$): the weights of the corresponding squares in the $$$i$$$-th row.
It is guaranteed that at least one of the weights $$$p_{i,j}$$$ is not equal to $$$0$$$.
Output the expected value of the area of painted grass modulo $$$10^9 + 7$$$.
Formally, let $$$M = 10^9 + 7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.
3 40 1 1 91 4 1 18 1 0 1
2
5 547 39 34 40 9284 43 40 42 8915 22 64 18 3863 61 26 48 5790 88 21 26 83
400000006
In the first example test, we can show that the expected value of the area of painted grass is equal to $$$2$$$.
You are given two integers $$$n$$$ and $$$2s$$$. Please note that the second integer is denoted by $$$s$$$ multiplied by $$$2$$$, although it can still be either even or odd.
In the rectangular coordinate system $$$Oxy$$$, find any polygon with $$$n$$$ sides and $$$n$$$ vertices such that:
- the $$$i$$$-th vertex has integer coordinates $$$(x_i, y_i)$$$, where $$$0 \le x_i, y_i \le 10^6$$$;
- its area is equal to $$$s$$$ (note: depending on whether $$$2s$$$ is even or odd, either $$$s$$$ or $$$s + \frac{1}{2}$$$ is an integer);
- its boundary does not touch or cross itself;
- no two vertices of the polygon coincide;
- no three consecutive vertices of the polygon lie on the same line.
If there are no such polygons, report this.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 20\,000$$$). The description of the test cases follows.
The only line of each test case contains two integers $$$n$$$ and $$$2s$$$ ($$$3 \le n \le 1000$$$, $$$1 \le 2s \le 10^6$$$): the number of vertices and the double area of a desired polygon.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$60\,000$$$.
For each test case, if a desired polygon does not exist, print the single word "NO" (without quotes).
Otherwise, in the first line, print the word "YES" (without quotes). In the $$$i$$$-th of the next $$$n$$$ lines, print two integers $$$x_i$$$ and $$$y_i$$$: the coordinates of the $$$i$$$-th vertex of a polygon that meets all the requirements. The vertices must be listed either clockwise or counterclockwise.
If there are multiple solutions, print any of them.
You may output the words in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
29 46 23
NO YES 1 1 2 2 2 3 1 4 5 4 6 1
In the first test case, we can show there are no $$$9$$$-gons with an area of $$$\frac{4}{2} = 2$$$ that meet all the requirements.
In the second test case, we have a desired $$$6$$$-gon with an area of $$$\frac{23}{2}$$$. Note that polygons may be non-convex.
You work at Interplanetary Clerks for Population Convenience, a company that handles various operations. In particular, your job is to assist people in filling out their visa applications for foreign embassies.
Today, you were shocked by the news: unexpectedly, the newly elected parliament of the planet Yllesynbelliawniffwrdd decided to abolish the usual calendar starting in the current year 2024 and create their own, with $$$n$$$ months and $$$a_1, a_2, \ldots, a_n$$$ days in them! It would be just a funny joke... if you didn't have to work with clients who now have to fill out their visa applications according to the new calendar.
The main difficulty, however, is calculating the desired duration of a visa. Clearly, if you arrive and depart the same month on the 5th and 17th days, respectively, then you need a 13-day visa, as both the arrival and departure days count. But what about longer trips? Fortunately for you, Yllesynbelliawniffwrdd does not issue visas that last more than a full year, so you don't have to worry about overly long time periods. However, since all the clients are asking for your help right now, you need to act really fast!
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100\,000$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le 100\,000$$$), denoting the number of months in the new calendar and the number of clients.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i \ge 1$$$, $$$\sum_{i=1}^{n} a_i \le 10^9$$$): the durations of the months.
Each of the next $$$m$$$ lines contains four integers $$$s_d$$$, $$$s_m$$$, $$$e_d$$$, $$$e_m$$$ ($$$1 \le s_m, e_m \le n$$$, $$$1 \le s_d \le a_{s_m}$$$, $$$1 \le e_d \le a_{e_m}$$$), meaning that the client wants to arrive on day $$$s_d$$$ of month $$$s_m$$$ and depart on day $$$e_d$$$ of month $$$e_m$$$. The departure day is less than a year away from the arrival day, so the year is not specified.
It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$100\,000$$$.
For each test case and each client, print a single integer $$$d$$$ ($$$1 \le d \le \sum_{i=1}^{n} a_i$$$), denoting the required minimum visa duration in days. Note that the answer never exceeds one year.
212 331 29 31 30 31 30 31 31 30 31 30 3116 11 15 1216 11 16 112 12 4 49 1998 244 353 998 244 353 998 244 3532 1 1 1
30 1 125 4785
In the first test case, the first client arrives on the day of the ICPC Belarus Regional Contest and departs on the day of the ICPC Northern Eurasia Finals. Their visa duration should be at least $$$30$$$ days.
In the last test case, the only client's visa should be issued for the entire year.
Laura has $$$n$$$ cards with positive integers written on them.
As today is November 16, 2024, she presents you with a special problem. Given a set of cards, determine if it is possible to choose some of them so that the number $$$16112024$$$ can be represented as the product of numbers written on the selected cards.
Of course, you cannot manipulate the numbers on the cards. For example, you cannot rotate a card with a $$$6$$$ to obtain a card with a $$$9$$$, tear cards into pieces, or write anything on them. However, if there exists a suitable set of cards, it is sufficient to find any such set.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 100\,000$$$): the number of cards.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \le a_i \le 10\,000$$$): the numbers written on the cards.
If there exists a set of cards whose product of numbers is equal to $$$16112024$$$, print the size of that set in the first line and the numbers themselves in the second line. You may print the numbers in any order.
Otherwise, print a single integer $$$0$$$ in the only line.
If there are multiple solutions, print any of them.
52 2 2 269 7487
5 2 2 2 269 7487
3998 244 353
0
A curious fact: the integers $$$2$$$, $$$269$$$, and $$$7487$$$ are prime. In other words, they have only two distinct positive integer divisors: $$$1$$$ and themselves.