Makoto told his friend, Sekai, who he secretly likes. However, it turned out to be a terrible idea, as she couldn't keep a secret and the information got spread around the class, eventually reaching the girl he likes. He is really angry at the situation, but what's done cannot be undone. To hopefully prevent anyone else from facing the same awkward situation, he decides to analyze this phenomenon.
Makoto has $$$N$$$ classmates, $$$M$$$ pairs of which are friends (friendship is mutual). It is guaranteed that for any two classmates $$$X$$$ and $$$Y$$$ there exist a chain of classmates $$$A_1, A_2,..., A_m$$$ such that the pairs $$$(X, A_{1}),(A_1, A_2),...,(A_{m-1}, A_m),(A_m, Y)$$$ are friends.
All of the $$$N$$$ classmates like to gossip. Hence, if one of these classmates receive some information, they will tell it to all their friends.
Makoto imagines $$$Q$$$ scenarios. Suppose classmate $$$C_i$$$ receives a message, and the message is not supposed to reach classmate $$$D_i$$$. He can bribe exactly one of these $$$N$$$ classmates (except classmate $$$C_i$$$ and $$$D_i$$$) to not spill his secret. He wants to know the number of people he can bribe to prevent the message from spreading to person $$$D_i$$$.
The first line of input contains two space-separated integers, $$$N, M$$$ ($$$3 \le N \le 200000, 1 \le M \le 200000$$$).
The next $$$M$$$ lines of input contain two space-separated integers each, $$$u, v$$$ ($$$1 \le u, v \le N, u \neq v$$$), denoting that classmates $$$u$$$ and $$$v$$$ are friends. It is guaranteed that no pair of classmates appear twice in the input, and for any two classmates $$$X$$$ and $$$Y$$$ there exist a chain of classmates $$$A_1, A_2,..., A_m$$$ such that the pairs $$$(X, A_{1}), (A_1, A_2), ..., (A_{m-1}, A_m), (A_m, Y)$$$ are friends.
The next line contains a single integer $$$Q$$$ ($$$1 \le Q \le 200000$$$), denoting the number of scenarios.
The next $$$Q$$$ lines of input contain two space-separated integers each, $$$C_{i}, D_{i}$$$ ($$$1 \le C_{i}, D_{i} \le N, C_{i} \neq D_{i}$$$), describing a scenario.
For each of the $$$Q$$$ scenarios, output a line containing a single integer, denoting the number of possible classmates Makoto can bribe to prevent the message from spreading from classmate $$$C_{i}$$$ to classmate $$$D_{i}$$$.
Subtask 1 (11 points): $$$N, M, Q \le 300$$$
Subtask 2 (20 points): $$$M = N - 1$$$
Subtask 3 (69 points): No additional constraints
9 14 1 2 1 3 3 4 3 5 4 5 4 7 5 6 5 7 6 7 1 8 1 9 2 9 2 8 9 8 3 3 8 1 3 4 9
1 0 2
This is how the friendship network looks like for the sample testcase.
In the first scenario, the only way to prevent the message from spreading from classmate $$$3$$$ to classmate $$$8$$$ is to bribe classmate $$$1$$$.
In the second scenario, there is no way to prevent the message from spreading from classmate $$$1$$$ to classmate $$$3$$$ since they are already friends (note that you can't bribe either of them).
In the third scenario, there are $$$2$$$ possible ways to prevent the message from spreading from classmate $$$4$$$ to classmate $$$9$$$: bribing classmate $$$1$$$ or classmate $$$3$$$.
There are $$$N$$$ students from a certain high school and each of them has a crush. Student $$$i$$$ has a crush on student $$$p_{i}$$$. Obviously, $$$p_{i} \neq i$$$ as a person cannot have a crush on themselves. For the purposes of this problem, the gender of the students doesn't matter, i.e. it is possible for a guy to have a crush on a guy and a girl to have a crush on a girl.
Consider the following process. Firstly, choose a random permutation $$$(a_1, a_2, ..., a_{N})$$$ of $$$1$$$ to $$$N$$$ (each with equal probability). On the $$$i$$$-th day, student $$$a_i$$$ (if they are not already taken) will confess to their crush, say X = student $$$p_{a_{i}}$$$.
What is the expected number of couples after the process ends? The answer can be written as an irreducible fraction $$$\frac{P}{Q}$$$. It can be proven that there exists a unique integer $$$0 \le R \lt 10^{9} + 7$$$ such that $$$QR \equiv P \pmod{10^{9}+7}$$$. Output the integer $$$R$$$.
The first line of input contains a single integer $$$N$$$ ($$$2 \le N \le 100$$$), denoting the number of students in the school.
The next line of input contains $$$N$$$ space-separated integers, the $$$i$$$-th of which denotes $$$p_{i}$$$ ($$$1 \le p_{i} \le N, p_{i} \neq i$$$).
Output a single integer, the value of $$$R$$$.
Subtask 1 (7 points): $$$N \le 9$$$
Subtask 2 (11 points): The graph with edges $$$i \rightarrow p_{i}$$$ form a directed cycle.
Subtask 3 (33 points): $$$N \le 40$$$
Subtask 4 (49 points): No additional constraints
3 2 3 1
1
4 2 3 1 1
166666669
2 2 1
1
9 4 9 4 9 4 9 4 9 4
1
10 6 3 7 3 8 3 9 3 10 3
362830693
For the first sample, there are $$$6$$$ possible permutations.
Suppose $$$a = (1, 2, 3)$$$. Then, student $$$1$$$'s confession will fail as student $$$2$$$ hasn't confessed. Student $$$2$$$'s confession will fail because student $$$3$$$ hasn't confessed. Student $$$3$$$'s confession will succeed and student $$$3$$$ and $$$1$$$ will form a couple.
You can check that any other permutation $$$a$$$ will give exactly $$$1$$$ couple.
Thus, the expected number of couples is $$$1$$$.
For the second sample, the expected number of couples is $$$\frac{7}{6}$$$, and $$$6 \times 166666669 \equiv 7 \pmod{10^{9} + 7}$$$. Thus, $$$R = 166666669$$$.
For example, consider $$$a = (3, 1, 2, 4)$$$. Then, student $$$3$$$'s confession will fail as student $$$1$$$ hasn't confessed. Student $$$1$$$'s confession will fail as student $$$2$$$ hasn't confessed. Student $$$2$$$'s confession will succeed and student $$$2$$$ and $$$3$$$ will form a couple. Student $$$4$$$'s confession will succeed and student $$$1$$$ and $$$4$$$ will form a couple. The number of couples in this case is $$$2$$$.
On the other hand, consider $$$a = (3, 2, 4, 1)$$$. Then, student $$$3$$$'s confession will fail as student $$$1$$$ hasn't confessed. Student $$$2$$$'s confession will succeed and student $$$2$$$ and $$$3$$$ will form a couple. Student $$$4$$$'s confession will fail as student $$$1$$$ hasn't confessed. Note that it doesn't matter here that student $$$1$$$'s crush, student $$$2$$$, is already taken at this point. Finally, student $$$1$$$'s confession will fail as student $$$2$$$ is already taken. The number of couples in this case is $$$1$$$.
For the third sample, both permutations $$$a = (1, 2), (2, 1)$$$ will leave students $$$1$$$ and $$$2$$$ as a couple. Thus, the expected number of couples is $$$1$$$.
Maria had a big fight with Kazuki and now wants to avoid him at all costs. Currently, Kazuki is at $$$(0, 0)$$$ in the coordinate plane, while Maria is at $$$(X, Y)$$$.
Maria wants to take a walk while maintaining a Manhattan distance strictly larger than $$$D$$$ from Kazuki, i.e. if her current coordinates is $$$(x, y)$$$, then $$$|x| + |y| \gt D$$$ must hold. Every second, she must choose one of the four cardinal directions (up, down, left, right) and move $$$1$$$ unit in that direction.
How many ways are there for her to take a walk without ever getting too close to Kazuki for $$$N$$$ seconds? Since the answer may be too large, print the answer modulo $$$10^{9} + 7$$$.
The first and only line of input contains four space-separated integers, denoting $$$X, Y, N, D$$$ ($$$|X|, |Y| \le 1500, |X| + |Y| \gt D, 1 \le N \le 1500, 0 \le D \le 4$$$) respectively.
Output a single integer, the number of ways for Maria to take a walk while keeping a distance from Kazuki for $$$N$$$ seconds, modulo $$$10^{9} + 7$$$.
Subtask 1 (9 points): $$$N \le 9$$$
Subtask 2 (17 points): $$$N \le 100$$$
Subtask 3 (25 points): $$$D=0$$$
Subtask 4 (49 points): No additional constraints
1 -1 2 1
8
6 2 18 0
998199851
1 4 9 4
73340
The following $$$8$$$ walks are valid for sample $$$1$$$:
$$$(1, -1) \rightarrow (1, -2) \rightarrow (1, -3)$$$
$$$(1, -1) \rightarrow (1, -2) \rightarrow (1, -1)$$$
$$$(1, -1) \rightarrow (1, -2) \rightarrow (2, -2)$$$
$$$(1, -1) \rightarrow (1, -2) \rightarrow (0, -2)$$$
$$$(1, -1) \rightarrow (2, -1) \rightarrow (3, -1)$$$
$$$(1, -1) \rightarrow (2, -1) \rightarrow (2, 0)$$$
$$$(1, -1) \rightarrow (2, -1) \rightarrow (2, -2)$$$
$$$(1, -1) \rightarrow (2, -1) \rightarrow (1, -1)$$$
On the other hand, the path $$$(1, -1) \rightarrow (0, -1) \rightarrow (0, -2)$$$ is invalid as the Manhattan distance between Maria's position and Kazuki's position is $$$1 \le D$$$ after $$$1$$$ second.
Kotaro and Akane like to chat with each other on LINE. However, they have found that replying to messages instantly every time can be too tiresome. They still do not want the other person to feel ignored though, so they came up with the following plan:
Firstly, they agree on a positive integer $$$T$$$. Every day, Kotaro will send a message at time $$$T$$$. Then, after every $$$T$$$ units of time, the person who last received a message will reply (hence Kotaro will send a message at time $$$T, 3T, 5T, ...$$$ and Akane will send a message at time $$$2T, 4T, 6T, ...$$$).
However, there are $$$N$$$ units of time per day and they cannot be online all the time. Specifically, Kotaro will be active during time $$$[a_1,b_1], [a_2,b_2],..., [a_X,b_X]$$$, while Akane will be active during time $$$[c_1,d_1], [c_2,d_2],..., [c_Y,d_Y]$$$ (here $$$[L,R]$$$ denotes the interval of time from time $$$L$$$ to time $$$R$$$ inclusive).
They want to choose the value of $$$T$$$ to ensure that they will be online to send the messages on time. How many values of $$$T$$$ from $$$1$$$ to $$$N$$$ can they choose?
The first line of input contains a single integer $$$N$$$ ($$$1 \le N \le 10^{9}$$$).
The next line of input contains a single integer $$$X$$$ ($$$1 \le X \le 300$$$), denoting the number of intervals of time when Kotaro will be online.
The next $$$X$$$ lines of input contain two space-separated integers each, denoting $$$a_i, b_i$$$ ($$$1 \le a_i \le b_i \le N$$$). It is guaranteed that $$$a_{i+1} \gt b_{i} + 1$$$ holds for all $$$1 \le i \le X - 1$$$.
The next line of input contains a single integer $$$Y$$$ ($$$1 \le Y \le 300$$$), denoting the number of intervals of time when Akane will be online.
The next $$$Y$$$ lines of input contain two space-separated integers each, denoting $$$c_i, d_i$$$ ($$$1 \le c_i \le d_i \le N$$$). It is guaranteed that $$$c_{i+1} \gt d_{i} + 1$$$ holds for all $$$1 \le i \le Y - 1$$$.
Output a single integer, the number of positive integers $$$T$$$ that Kotaro and Akane can choose.
Subtask 1 (9 points): $$$N \le 10^{6}$$$
Subtask 2 (40 points): $$$X = Y, a_{i} = c_{i}, b_{i} = d_{i}$$$ for all $$$1 \le i \le X$$$.
Subtask 3 (51 points): No additional constraints
10 2 2 4 6 9 3 1 3 5 7 9 10
5
10000000 1 4092001 5033941 2 206 314 1214 10000000
941941
For the first sample, they can choose the values $$$T = 3, 6, 7, 8, 9$$$.
If $$$T = 6, 7, 8, 9$$$ is chosen, then only one message will be sent per day and Kotaro is active at the time.
If $$$T = 3$$$ is chosen, then Kotaro sends a message at time $$$3, 9$$$ while Akane sends a message at time $$$6$$$, and they are indeed active during these times.
Note that $$$T = 2$$$ fails because Akane is not active at time $$$4$$$, while $$$T = 5$$$ fails because Kotaro is not active at time $$$5$$$.
It's Valentine's Day and Takitsubo wants to make a chocolate bar for Hamazura! The chocolate bar can be pictured as a rectangular grid, where each cell has an integer value of sweetness.
Hamazura likes to cut out a $$$1 \times K$$$ or $$$K \times 1$$$ subrectangle from the chocolate bar and eat it first (here $$$K$$$ is any positive integer). A $$$1 \times K$$$ (or $$$K \times 1$$$) subrectangle of the chocolate bar is delicious if the sweetness level of the cells are strictly monotonic, i.e. strictly decreasing or increasing from left to right (or top to bottom).
Takitsubo knows that Hamazura's favourite number is $$$X$$$, so she wants to create the chocolate bar so that there are exactly $$$X$$$ ways to cut out a delicious $$$1 \times K$$$ or $$$K \times 1$$$ subrectangle. Can you help her create such a chocolate?
There will be multiple testcases per test file.
The first line of input contains a single integer $$$T$$$ ($$$1 \le T \le 50$$$), denoting the number of testcases.
The next $$$T$$$ lines of input contain a single integer $$$X$$$ ($$$1 \le X \le 7995051$$$), denoting Hamazura's favourite number.
For each test case, output two space-separated integers, $$$N, M$$$ ($$$1 \le N, M \le 200$$$) on the first line, denoting the dimensions of the chocolate bar.
The next $$$N$$$ lines should contain $$$M$$$ space-separated integers each, where the numbers in the $$$i$$$-th line denote the sweetness level of the cells in the $$$i$$$-th row. All sweetness levels must be a nonnegative integer not exceeding $$$10^{6}$$$.
Subtask 1 (3 points): $$$X \le 200$$$
Subtask 2 (14 points): $$$X \le 40000$$$
Subtask 3 (20 points): $$$2222222 \le X \le 3333333$$$
Subtask 4 (20 points): $$$X \le 4567890$$$
Subtask 5 (20 points): $$$X \le 6666666$$$
Subtask 6 (11 points): $$$X \le 7777777$$$
Subtask 7 (12 points): No additional constraints
7 3 14 1 4 9 7 113
1 2 2 14 2 3 9 4 1 2 0 2 1 1 1 3 1 3 1 1 1 5 2 1 0 1 1 2 2 14 2 20 20 6 6 0 1 2 3 4 6 7 1 2 3 8 5 3 6 0 1 4 4 2 5 0 4 4 1 9 7 5 1 0 3 0 6 2 4 4 9
Let's look at the second testcase, $$$X = 14$$$.
There are $$$6$$$ ways to cut out a $$$1 \times 1$$$ delicious subrectangle, namely each of the $$$6$$$ cells of the chocolate bar.
There are $$$3$$$ ways to cut out a $$$2 \times 1$$$ delicious subrectangle, namely each of the $$$3$$$ columns of the chocolate bar.
There are $$$4$$$ ways to cut out a $$$1 \times 2$$$ delicious subrectangle, as all possible $$$1 \times 2$$$ subrectangles you can cut out are delicious.
There is one way to cut out a $$$1 \times 3$$$ delicious subrectangle, namely the top row of the chocolate bar.
Note that the $$$1 \times 3$$$ subrectangle corresponding to the bottow row of the chocolate bar is not delicious, because it is neither strictly increasing from left to right or right to left.
Hence, there are a total of $$$6 + 3 + 4 + 1 = 14$$$ ways to cut out a delicious $$$1 \times K$$$ or $$$K \times 1$$$ subrectangle, as desired.
You can verify the other sample cases by hand.
This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().
Nibutani and Dekomori are fighting with each other again. This time, their battle is about filling blanks in a string.
A string $$$S$$$ is written on the blackboard, where each character is either L, O, V, E or ?. Nibutani and Dekomori takes turn replacing one of the question marks in the string with one of the letters L, O, V or E. Nibutani plays first. The game ends when all question marks are replaced.
Nibutani wants to maximize the number of substrings that is equal to LOVE while Dekomori wants to minimize the number of such substrings. A substring is defined as a string obtained by removing several (possibly zero) characters from the beginning and the end of the original string.
You, as our main protagonist Yuuta, are tired of their endless battles. Thus, you want to write a program that will help them play the game optimally. Can you perform this task?
The first line of input contains the initial string $$$S$$$ ($$$1 \le |S| \le 200000$$$). The next line contains a single integer $$$T$$$ ($$$1 \le T \le 2$$$), where $$$T = 1$$$ means that you are playing as Nibutani while $$$T = 2$$$ means that you are playing as Dekomori.
Whenever it is your turn, you should output an integer $$$p$$$ ($$$1 \le p \le |s|$$$) and a character $$$c$$$ ($$$c \in \{L, O, V, E\}$$$), separated with a space. This denotes that you will place the character $$$c$$$ at position $$$p$$$. The character at position $$$p$$$ must be a question mark before you replace it.
Whenever it is the other player's turn, you should read an integer and a character (given in the same format as your output), denoting the other player's move.
Your program should terminate when all question marks are replaced.
Remember to flush the output after outputting every line.
Your solution will be accepted if the result of the game is at least as good as the result when both sides play optimally.
Subtask 1 (40 points): $$$|S| \le 3000$$$
Subtask 2 (30 points): $$$T = 1$$$
Subtask 3 (30 points): $$$T = 2$$$
L?VEE?O?? 1 6 L 8 L
2 O 9 E
Initially, the string is L?VEE?O??. You play as Nibutani.
After your first move, the string is LOVEE?O??.
After Dekomori's first move, the string is LOVEELO??.
After your second move, the string is LOVEELO?E.
After Dekomori's second move, the string is LOVEELOLE.
After the game, the number of substrings LOVE in the string is $$$1$$$. It can be proven that this is the best possible result with optimal play from both sides.
Yamada and Shiraishi are planning a honeymoon trip. They have looked at $$$N$$$ tourist destinations, numbered from $$$1$$$ to $$$N$$$. The $$$i$$$-th tourist destination increases Yamada's happiness value by $$$a_{i}$$$ and Shiraishi's happiness value by $$$b_{i}$$$.
A trip consists of visiting the tourist destinations $$$l, l+1,..., r$$$ in order, one per day. Initially, both of their happiness values are $$$0$$$. After every day of the trip, they compute their combined happiness for the day, which is the maximum of both of their current happiness values (because Yamada is happy if Shiraishi is happy and vice versa). Finally, the total happiness of the trip is the sum of their combined happiness over all $$$r-l+1$$$ days (see the samples for an example).
Yamada and Shiraishi made $$$Q$$$ possible trip plans. The $$$i$$$-th plan consists of them visiting the tourist destinations from $$$l_{i}$$$ to $$$r_{i}$$$ in this order. Can you help them calculate the total happiness of each plan?
The first line of input contains two space-separated integers, $$$N, Q$$$ ($$$1 \le N, Q \le 500000$$$).
The next line of input contains $$$N$$$ space-separated integers, denoting the values $$$a_{i}$$$ ($$$-10^{6} \le a_{i} \le 10^{6}$$$).
The next line of input contains $$$N$$$ space-separated integers, denoting the values $$$b_{i}$$$ ($$$-10^{6} \le b_{i} \le 10^{6}$$$).
The next $$$Q$$$ lines of input contain $$$2$$$ space-separated integers each. The $$$i$$$-th such line contains the values $$$l_{i}, r_{i}$$$ ($$$1 \le l_{i} \le r_{i} \le N$$$).
Output $$$Q$$$ lines containing a single integer each: the total happiness of each plan.
Subtask 1 (4 points): $$$N, Q \le 5000$$$
Subtask 2 (7 points): $$$N, Q \le 150000, a_{i} \ge 0, b_{i} = 0$$$ for all $$$1 \le i \le N$$$
Subtask 3 (21 points): $$$N, Q \le 150000, b_{i} = 0$$$ for all $$$1 \le i \le N$$$
Subtask 4 (37 points): $$$N, Q \le 150000$$$
Subtask 5 (31 points): No additional constraints
6 7 3 -5 8 -10 3 7 -4 20 9 -100 105 20 1 6 1 5 2 4 3 3 3 6 2 5 4 5
120 70 42 9 55 76 -5
1 1 -110 318 1 1
318
Consider the first trip of the first sample.
Before the trip starts: Yamada's happiness = $$$0$$$, Shiraishi's happiness = $$$0$$$.
After day $$$1$$$: Yamada's happiness = $$$3$$$, Shiraishi's happiness = $$$-4$$$, Combined happiness = $$$3$$$.
After day $$$2$$$: Yamada's happiness = $$$3-5=-2$$$, Shiraishi's happiness = $$$-4+20=16$$$, Combined happiness = $$$16$$$.
After day $$$3$$$: Yamada's happiness = $$$-2+8=6$$$, Shiraishi's happiness = $$$16+9=25$$$, Combined happiness = $$$25$$$.
After day $$$4$$$: Yamada's happiness = $$$6-10=-4$$$, Shiraishi's happiness = $$$25-100=-75$$$, Combined happiness = $$$-4$$$.
After day $$$5$$$: Yamada's happiness = $$$-4+3=-1$$$, Shiraishi's happiness = $$$-75+105=30$$$, Combined happiness = $$$30$$$.
After day $$$6$$$: Yamada's happiness = $$$-1+7=6$$$, Shiraishi's happiness = $$$30+20=50$$$, Combined happiness = $$$50$$$.
The total happiness of the trip is $$$3+16+25-4+30+50=120$$$.
For the third query, the combined happiness for the three days are $$$20, 29, -7$$$ respectively, with a total happiness of $$$20+29-7=42$$$.