"Tinkoff" is rebranding! According to the latest trends, it was decided that the new logo is going to be in a checkered pattern. The new logo will be a shape made of $$$1 \times 1$$$ squares, such that any two squares that share a side are of different colors: one black and one white. The logo also has to be connected: it is possible to reach any square from any other, moving between the side-adjacent squares.
The brand book states that the logo must have exactly $$$w$$$ white squares and $$$b$$$ black squares. So that the logo doesn't look too dark or too bright, $$$b \le w \le 3b + 1$$$ must hold.
The brand team brought checkered pattern sheets to start printing new "Tinkoff" logos. Every sheet is a rectangle with $$$4n$$$ rows and $$$4m$$$ columns, the top left square of each sheet is black. You are tasked to cut the new logo out of them. Just to be sure, the brand team ordered the sheets of a large enough size: the number of black squares in the logo $$$b$$$ doesn't exceed $$$nm$$$.
Your task is to design a connected logo consisting of $$$b$$$ black and $$$w$$$ white squares such that it fits into the rectangular sheet of size $$$4n \times 4m$$$. The company analysts proved that on the sheet of size $$$4n \times 4m$$$, one can always make a logo provided that both $$$b \le w \le 3b + 1$$$ and $$$b \le nm$$$ hold.
The input consists of several tests.
The first line contains an integer $$$t$$$ — the number of tests in the input ($$$1 \le t \le 2\,000$$$). Then, $$$t$$$ tests follow, each one on a separate line.
The test description consists of four integers $$$n$$$, $$$m$$$, $$$b$$$, $$$w$$$ ($$$1 \le n, m \le 50$$$; $$$0 \le b \le n \cdot m$$$; $$$b \le w \le 3b + 1$$$).
The total sum of $$$4n \cdot 4m$$$ of all tests in a single input doesn't exceed $$$2 \cdot 10^5$$$.
Print the grid of size $$$4n \times 4m$$$ with the logo for each test. 'W' character stands for the white square, 'B' — for the black square, and '.' — for the square that doesn't belong to the logo.
Any connected logo with $$$w$$$ white squares and $$$b$$$ black squares will be accepted.
| Subtask | Score | Constraints |
| 1 | 20 | $$$b = w$$$ |
| 2 | 25 | $$$b \le 2m - 1$$$ |
| 3 | 25 | $$$b \le 2(n + m) - 3$$$ |
| 4 | 30 | No additional constraint |
2 2 3 5 7 2 2 4 8
............ ..WBWBWBW... .....W...... .....B...... .....W...... .....B...... .....W...... ............ ........ ........ ...W.W.. ..WBWB.. ...W.W.. ..WBWB.. ........ ........
This is an interactive problem.
The jury has chosen a secret five-digit prime number (without leading zeros). Your task is to guess this number. Whenever you make a guess, the jury's program will tell you which digits are correct and which ones are present but are currently in the wrong place.
Consider an example where the jury has chosen 19937 and your guess is 31357. The response for your guess will be ??-{}-+: the last 7 is in the correct place; the first two digits appear in the number but in other places. Note that the second occurrence of $$$3$$$ is marked as a - because there is only one $$$3$$$ in the secret prime number.
A more formal description of the response: let the secret prime be $$$S = s_1 s_2 s_3 s_4 s_5$$$ and your guess it $$$T = t_1 t_2 t_3 t_4 t_5$$$. For every $$$i$$$ such that $$$s_i = t_i$$$, the response will contain +. Let's call all such places used. For every remaining index, going from left to right, we'll make the following check: if $$$t_i$$$ is present among the yet unused digits in $$$S$$$, then the $$$i$$$-th character of the response will contain ?, and the corresponding digit in $$$S$$$ is marked as used. All remaining characters in the response will be -.
This game has two different modes: an easy mode and a hard mode. In easy mode, you are allowed to guess any five-digit with (possibly, with leading zeros). In hard mode, all your guesses have to be five-digit primes (without leading zeros). In addition, there is a limit on the number of guesses you can make for each subtask.
Each test will contain $$$T$$$ rounds. In every round, you have to guess a secret prime number. The prime numbers in each test are chosen beforehand and will be the same throughout the contest.
You should start the interaction by reading a string describing the current mode and $$$L$$$ — the maximum number of guesses you can make during each round. The easy mode is described by the string «easy», and the hard mode is described by the string «hard».
Then, you should read the integer $$$T$$$ ($$$1 \le T \le 10$$$) — the number of rounds in the current test.
Every round starts with your program sending a five-digit string. In hard more, this string should denote a five-digit prime number without leading zeros. In easy mode, there are no restrictions on this five-digit string. Then, the jury program sends the response — a string with five characters -, ?, or +. If you either violated the interaction protocol or didn't guess the secret prime number on your $$$L$$$-th attempt, you will receive !!!!! as a response. After receiving such a response, you should terminate your program.
After receiving the +++++ response, the next round will start immediately. If it was the last round, finish the execution. Don't forget to print the line break character or flush the output after each guess.
| Subtask | Points | Hard mode? | Constraints | Required subtasks |
| 1 | 7 | $$$-$$$ | $$$L = 100$$$ | – |
| 2 | 11 | $$$+$$$ | $$$L = 100$$$ | 1 |
| 3 | 8 | $$$-$$$ | $$$L = 10$$$ | 1 |
| 4 | 15 | $$$+$$$ | $$$L = 10$$$ | 1,2,3 |
| 5 | 12 | $$$-$$$ | $$$L = 7$$$ | 1,3 |
| 6 | 16 | $$$+$$$ | $$$L = 7$$$ | 1,2,3,4,5 |
| 7 | 14 | $$$-$$$ | $$$L = 5$$$ | 1,3,5 |
| 8 | 17 | $$$+$$$ | $$$L = 5$$$ | 1,2,3,4,5,6,7 |
easy 10 1 -??+- -+--? +++++
12345 78778 28843
hard 5 1 ??--+ ?+--? +++++
31357 99083 19937
You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Find an array of non-negative integers $$$c$$$ of length $$$n$$$ such that if you add it to $$$a$$$ and $$$b$$$ element-wise, then the product of the numbers in each one of these arrays is the same, or say that it's impossible.
Formally, you need to find a sequence of non-negative integers $$$c_1, c_2, \ldots, c_n$$$, such that $$$(a_1 + c_1) \cdot (a_2 + c_2) \cdot \ldots \cdot (a_n + c_n) = (b_1 + c_1) \cdot (b_2 + c_2) \cdot \ldots \cdot (b_n + c_n)$$$.
The first line contains one integer $$$n$$$ ($$$1 \le n \le 100\,000$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$).
The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 1000$$$).
If such array does not exist, output "NO". Otherwise, print "YES" in the first line. Then, print $$$n$$$ integers $$$c_1, c_2 \ldots c_n$$$ ($$$0 \le c_i \le 10^{18}$$$) — the solution to the problem. If there are multiple solutions, print any of them. It's guaranteed that if a solution exists, then there is a solution that fits the constraints.
| Subtask | Points | Constraints |
| 1 | 9 | $$$n \le 2; a_i, b_i \le 10$$$ |
| 2 | 25 | $$$n \le 2$$$ |
| 3 | 19 | $$$n \le 3$$$ |
| 4 | 18 | $$$a_i, b_i \le 2$$$ |
| 5 | 29 | No additional constraints |
4 1 2 5 4 6 1 6 2
YES 6 4 1 1
Julia's dream has finally come true! She became the head of the Department of General Innopolis Management! In her department, everything is done in the most modern way: bureaucracy proceeds using the latest generation software.
There are $$$n$$$ employees in the department, each one of them has a dedicated computer. Let us number them with unique integer IDs from $$$1$$$ to $$$n$$$. Some pairs of computers are connected with a cable, which allows transferring data in both ways. Besides that, there is exactly one way to transfer data via cables between each two given computers, if we only allow using each cable at most once. In other words, the network of computers and cables forms a tree.
Currently, the department works on $$$k$$$ draft laws. Julia has to make a work schedule for tomorrow: for every employee, she has to decide which one out of $$$k$$$ draft laws they will work on. Every employee must work on exactly one draft law throughout the day. A draft law can be edited on several computers at once (or even on no computers). However, there is an exception: two computers connected with a cable must work on different draft laws to avoid concurrency issues. Also, some employees are assigned to a specific draft law, and they will only work on that law.
Julia is very excited for her first working day, and she is curious about the number of ways to create a work schedule for tomorrow. Help her find the desired number of ways! Since the answer may be too large, find the answer modulo $$$10^9+7$$$.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$) — the number of computers in the department and the number of draft laws in development.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le k$$$), where $$$a_i$$$ is the number of a draft law of the $$$i$$$-th employee is assigned to, or $$$0$$$ if they are ready to work on anything.
The next $$$n - 1$$$ lines contain two integers $$$u_j$$$ and $$$v_j$$$ each — IDs of computers connected with a cable ($$$1 \le u_j, v_j \le n$$$; $$$u_j \neq v_j$$$). It is guaranteed that the network of computers and cables forms a tree.
Print a single integer — the number of ways to make a work schedule for tomorrow, modulo $$$10^9+7$$$.
| |} Subtask | Points | Constraints |
| 1 | 5 | $$$n, k \le 8$$$ |
| 2 | 5 | $$$k = 2$$$ |
| 3 | 5 | all $$$a_i$$$ are to $$$0$$$ |
| 4 | 10 | $$$n, k \le 300$$$ |
| 5 | 15 | $$$n, k \le 3000$$$ |
| 6 | 20 | $$$n \le 3000$$$ |
| 7 | 10 | Each computer is connected to at most two other computers |
| 8 | 20 | $$$n \le 10^5$$$ |
| 9 | 10 | No additional constraints |
4 3 0 0 1 2 1 2 2 3 2 4
2
4 3 1 0 0 0 1 2 2 3 2 4
8
4 1000000000 0 2 2 0 1 2 2 3 3 4
0
In the first example, computers $$$3$$$ and $$$4$$$ are already assigned with draft laws $$$1$$$ and $$$2$$$, so for computer $$$2$$$ there is only one possible draft law: $$$3$$$. And for computer $$$1$$$, we can choose two draft laws ($$$1$$$ and $$$2$$$), so the answer is $$$2$$$.
In the third example two connected computers $$$2$$$ and $$$3$$$ are already assigned with the same draft law $$$2$$$. Therefore, no plan can satisfy the requirements.