Phitsanulok province and the city of Phitsanulok was called "the city of two rivers" because it is located between Nan River and Khwae Noi River. Phitsanulok province is a big province and it is easy to travel to many famous tourist destinations such as Phu Hin Rong Kla National Park, Thung Salaeng Luang National Park, Man Daeng Waterfall, and Kang Song Waterfall. Following the border opening after the COVID emergency has passed, Prof. TOI of POSN.NU. is tasked to plan the promotion of tourism within the province. For his research to follow the academic standards, Prof. TOI assigns two research assistants who are proficient in digital systems, Mr. X and Mr. Y, the task of surveying electric vehicle charging stations, reporting the location and the number of charging outlets at each station, throughout routes to tourist destinations in order to help tourists with electric vehicles plan energy management for their vehicles. Prof. TOI asks Mr. X to survey AC (alternating current) charging stations and Mr. Y to survey DC (direct current) charging stations, where the results will be further used for the task. When Mr. X measures the distances, he measures from the westernmost edge of Phitsanulok province towards the east. (If the distance is negative, the location is to the west of Phitsanulok.)
Mr. X's report includes $$$N$$$ AC charging stations, where the distance to each station is $$$x_1,x_2,\ldots,x_N$$$ units, and the number of charging outlets at each station is $$$s_1,s_2,\ldots,s_N$$$. Mr. Y uses the same distance measurement scheme. Mr. Y's report includes $$$M$$$ DC charging stations, where the distance to each station is $$$y_1,y_2,\ldots,y_M$$$ units, and the number of charging outlets at each station is $$$t_1,t_2,\ldots,t_M$$$. Prof. TOI then takes both of their reports to calculate and design the tourism plan. However!!! suddenly a problem emerges. Prof. TOI receives a report that Mr. Y misunderstands the reporting procedure, collecting and recording incorrect distance values in the report. Prof. TOI needs to quickly correct the mistakes and deliver the results before he can make it to the opening ceremony of the Olympiad in Informatics. Prof. TOI discovers that the mistakes exhibit a linear pattern, and thus he can take the distances $$$y_1,y_2,\ldots,y_M$$$ and recalculate them into
$$$\bar y_j = \alpha y_j+\beta$$$ for $$$j=1,\ldots,M$$$
Because of limited timeframe, Prof. TOI has to merge the data from Mr. X and Mr. Y in order to create the TOI-chart to help with planning. The horizontal axis values of the chart are the values of $$$x_i$$$ for $$$i=1,\ldots,N$$$, or $$$\bar y_j$$$ for $$$j=1,\ldots,M$$$, sorted in increasing order, and the vertical axis values are the number of charging outlets $$$s_i$$$ for $$$i=1,\ldots,N$$$, or $$$t_j$$$ for $$$j=1,\ldots,M$$$, unless $$$x_i=\bar y_j$$$ for some $$$i$$$, $$$j$$$, in which case the vertical axis values are the number of charging outlets $$$s_i+t_j$$$. Then, Prof. TOI needs to take the merged location and outlet count numbers to create the new data, with the locations $$$z_k$$$ for $$$k=1,\ldots,P$$$, where $$$z_1 \lt z_2 \lt \cdots \lt p$$$, and the number of charging outlets $$$u_1,u_2,\ldots,u_P$$$, respectively. The data is then analyzed into slots, where the number of slots is $$$u_1+u_2+\ldots+u_P$$$ and
- slots $$$i=1,\ldots,u_1$$$ have value $$$z_1$$$
- slots $$$(u_1+1),\ldots,(u_1+u_2)$$$ have value $$$z_2$$$
- ...
- slots $$$(u_1+\cdots+u_{P-1}+1),\ldots,(u_1+\cdots+u_{P-1}+u_P)$$$ have value $$$z_P$$$
Example
Mr. X's report includes distances to each of the $$$N=9$$$ charging stations and the number of AC charging outlets as follows:
| station $$$i$$$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| $$$x_i$$$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 |
| $$$s_i$$$ | 1 | 2 | 1 | 3 | 5 | 7 | 6 | 2 | 1 |
Mr. Y's report includes distances to each of the $$$M=8$$$ charging stations and the number of DC charging outlets as follows:
| station $$$j$$$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| $$$y_j$$$ | 1 | 2 | 4 | 5 | 6 | 7 | 9 | 10 |
| $$$t_j$$$ | 1 | 2 | 4 | 6 | 3 | 2 | 2 | 1 |
Figure 1. Charts displaying the relationship between distances and charging outlet counts from (a) Mr. X's report, and (b) Mr. Y's report Prof. TOI corrects the report using $$$\alpha=2$$$ and $$$\beta=−5$$$ to obtain new Mr. Y's report with modified $$$\bar y_j = 2y_j − 5$$$
| station $$$j$$$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| $$$y_j$$$ | -3 | -1 | 3 | 5 | 7 | 9 | 13 | 15 |
| $$$t_j$$$ | 1 | 2 | 4 | 6 | 3 | 2 | 2 | 1 |
Figure 2. Corrected Mr. Y's report 
Figure 3. Example of distance measurement From Mr. X's report and corrected Mr. Y's report, the merged data and TOI-chart appear as follows:
| station $$$k$$$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | $$$P=14$$$ |
| $$$z_k$$$ | -3 | -1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 13 | 15 |
| $$$u_k$$$ | 1 | 2 | 1 | 2 | 5 | 3 | 11 | 7 | 9 | 2 | 2 | 1 | 2 | 1 |
Figure 4. TOI-chart created by Prof. TOI When the data from TOI-chart is analyzed into slots, the result is as follows:
| slot | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ... | 46 | 47 | 48 | 49 |
| value | -3 | -1 | -1 | 1 | 2 | 2 | 3 | 3 | 3 | ... | 10 | 13 | 13 | 15 |
From the example above, the value at slot 1 is -3, the values at slots 2 and 3 are -1 ... the value at slot 48 is 13, and the value at slot 49 is 15.
Your Task
Write an efficient program to determine the value at slot $$$k$$$.
There are $$$Q+5$$$ lines of input:
| Line 1 | 3 integers separated by a single space. The first integer is $$$N$$$, denoting the number of AC charging stations recorded by Mr. X. The second integer is $$$M$$$, denoting the number of DC charging stations recorded by Mr. Y. The third integer is $$$Q$$$, denoting the number of questions asking for the values at slot $$$k$$$. Let $$$1 \leq N,M \leq 100{,}000$$$ and $$$0 \leq Q \leq 50{,}000$$$. |
| Line 2 | $$$N$$$ integers separated by a single space, denoting the distance of $$$x_1, x_2, \ldots , x_N$$$ units to each charging station, as recorded by Mr. X. Let $$$1 \leq x_1 \lt x_2 \lt \ldots \lt x_N \leq 1{,}000{,}000$$$. |
| Line 3 | $$$N$$$ integers separated by a single space, denoting the number of AC charging outlets $$$s_1, s_2, \ldots, s_N$$$ at each charging station, as recorded by Mr. X. Let $$$1 \leq s_i \leq 100$$$ for $$$i = 1, ... ,N$$$. |
| Line 4 | $$$M$$$ integers separated by a single space, denoting the distance of $$$y_1, y_2, \ldots , y_M$$$ units to each charging station, as recorded by Mr. Y. Let $$$1 \leq y_1 \lt y_2 \lt \ldots \lt y_m \leq 1{,}000{,}000$$$. |
| Line 5 | $$$M$$$ integers separated by a single space, denoting the number of DC charging outlets $$$t_1, t_2, \ldots, t_M$$$ at each charging station, as recorded by Mr. Y. Let $$$1 \leq t_j \leq 100$$$ for $$$j = 1, \ldots ,M$$$ |
| Line $$$l+5$$$ to Line $$$Q+5$$$ for $$$l = 1,\ldots,Q$$$ | 3 integers separated by a single space. The first integer is $$$\alpha_l$$$ where $$$1 \leq \alpha_l \leq 100$$$. The second integer is $$$\beta_l$$$ where $$$-10^6 \leq \beta_l \leq 10^6$$$, for calculating $$$\bar y_j = \alpha y_j+\beta$$$. The third integer is $$$k_l$$$ denoting the slot position $$$k_l$$$ where $$$1 \leq k_l \leq \sum_i s_i + \sum_j t_j$$$ |
There are $$$Q$$$ lines of output:
| Line $$$l$$$ | Each line contains 1 integer denoting the data at slot $$$k_l$$$ for $$$l=1,\ldots,Q$$$ |
Notices regarding the test sets are as follows:
| Test Group | Maximum attainable score in this group | Condition(s) |
| 1 | 8 | $$$1\leq N,M,Q \leq 100$$$ |
| 2 | 13 | $$$x_i = i$$$, $$$\forall i$$$ and $$$y_j = j$$$, $$$\forall j$$$ and $$$N, M \lt 5{,}000$$$ and $$$Q \lt 10{,}000$$$ |
| 3 | 17 | $$$\alpha=1$$$ and $$$\beta=0$$$ |
| 4 | 22 | $$$N=1$$$ and $$$s_1=1$$$ |
| 5 | 40 | No additional constraints |
9 8 8 1 2 3 4 5 6 7 8 10 1 2 1 3 5 7 6 2 1 1 2 4 5 6 7 9 10 1 2 4 6 3 2 2 1 1 0 1 1 0 2 1 0 3 1 0 8 2 -5 1 2 -5 2 2 -5 3 2 -5 8
1 1 2 4 -3 -1 -1 3
5 2 6 1 2 3 4 5 1 1 1 1 1 1 5 1 1 1 0 1 1 0 3 1 1 1 1 1 3 1 -2 1 1 -2 3
1 2 1 2 -1 2
5 2 6 1 2 3 4 5 1 1 1 1 1 1 5 1 1 1 -5 1 1 -5 2 1 -5 3 3 -10 3 3 10 3 3 20 3
-4 0 1 2 3 3
Recommended programming tips
If the contestant uses cin/cout, it is recommended to add 2 lines as the following:
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
After Professor TOI has done his initial planning to promote tourism, in order to ensure the completeness of the work, he sent a research assistant Mr. K to explore the tourist attractions seriously. However!!! There is a problem once again. While Mr. K was travelling to explore the new attractions, Mr. K got stuck in a maze. Fortunately, Mr. K has a heritage, which is the cryptic writing, that has been passed from generations to generations for 19 generations. Therefore, he knows that the maze consists of $$$N$$$ rooms. Each of the rooms has a number labeled between $$$1$$$ to $$$N$$$, none of which are repeated. There is a total of $$$N-1$$$ pathways between the rooms such that it is always possible to walk between one room to any other rooms using these pathways.
Since the heritage is an old piece of data, and has been written using ancient ways, to prevent errors, Mr. K then chose to investigate the maze once again to update the data. This means, if the entrance of the maze is at room $$$x$$$, Mr. K will use the exploration algorithm learned from his first and second training camp, which is exactly the following.
- Mr. K has an "exploration list" at the start. This list will be an empty list and when Mr. K go into any room of the maze, he might take note the number of that room, "appending" into the list. The number will be written if and only if the room hasn't been in the list before. Mr. K starts exploring by walking into the room $$$x$$$ and write $$$x$$$ into the "list".
- Once Mr. K gets into any room, he will choose one of the pathways to exit that room by the following procedure.
- If there exists a pathway leading into a room that he hasn't been there before, Mr. K will choose the pathway and walk into that room (and he will simultaneously write down the number of the new room according to the first step of the algorithm). If there are multiple ways of choosing the next room, he may choose any of the options.
- However, if all pathways lead into rooms that he has already been in before, Mr. K will check whether the current room is $$$x$$$ or not. If not, Mr. K will walk into the pathway leading to the room appearing on the topmost of the "list" and walk inside that room. But if the current room is $$$x$$$, Mr. K will know that he has explored the entire maze already, so he will end his exploration, which leads him outside of the maze.
- Once he exits the maze, Mr. K will submit "the list" as a result of his exploration to Professor TOI.
For example, if the maze consists of three rooms, with pathways connecting room 1 to room 2, and room 2 to room 3, as shown in Fig 1.
Fig 1. A maze consisting of pathways connecting room 1 to room 2 and room 2 to room 3. For the case that the entrance $$$x$$$ is room 1, Mr. K will walk and record his exploration list as the following. He starts walking into room 1 and the "list" of Mr. K is [1], or as shown in the following table.
| 1 |
From room 1, there is a pathway to room 2, which is the room that Mr. K has never been to. Hence, Mr. K then walks into room 2 and the "list" of Mr. K is now [1, 2] or as shown in the following table.
| 1 |
| 2 |
From room 2, there are two pathways leading into room 1 and room 3, where Mr. K will only choose room 3 because it's the only room he hasn't been to before. Now, his list will be [1 2 3] or as shown in the following table.
| 1 |
| 2 |
| 3 |
From room 3, there is only one pathway leading to room 2, where he has already gone there, so he must go there because it is the topmost number appearing in his list. And his list will be the same, that is [1 2 3].
From room 2, there are two pathways leading to room 1 and room 3. Mr. K must go to room 1 because it's the room appearing in the topmost position on his list.
Now Mr. K is inside room $$$x = 1$$$, so Mr. K ends his journey and immediately quits the maze. Observe that for the case of the entrance $$$x$$$ equals 1, there is only one possibility of the "list", that is, [1 2 3].
Observe that if two people explore the same maze, they might come back with two different "list"s. For example, in the same case as in Fig 1., if the entrance $$$x$$$ is room 2, there will be two possibilities of the "list": [2 1 3] and [2 3 1].
However, we don't know the explicit structure of the maze. We only have a "list" from the result of a historical explorer, which has been passed from generations to generations. And the explorers in the past used a different method of writing down the data. The difference is at step 1 of the algorithm where the old ways of doing this is that no matter whether one has been to the room or not, the explorer will always write down the number of that room, appending into the end of the list. The exploration is still the same, i.e., only explore the unexplored rooms (both the step 2 and step 3 of the algorithm are the same between the old way and the current way). For example, if the old explorer explores the maze from Fig 1., starting from the entrance $$$x$$$ being room 2, the explorer might write down either [2 1 2 3 2] or [2 3 2 1 2] (both ways are possible).
Your Task
Write an efficient program to compute the number of ways to write the exploration list using Mr. K's algorithm (the current one), answering the remainder of the answer with 1,000,000,007.
There are 2 lines of input:
| Line 1 | A single integer $$$N$$$ denoting the number of rooms, where $$$1 \leq N \leq 500,000$$$. |
| Line 2 | $$$2N-1$$$ integers, each separated by a space, representing the exploration list obtained using the old algorithm. Observe that the first number of the list is the entrance, which will always be matching with the last number. |
There is 1 line of output:
| Line 1 | One integer denoting the number of possibilities of the exploration list obtained using Mr. K's algorithm, where the output should be the remainder from dividing the answer by 1,000,000,007. |
Notices regarding the test sets are as follows:
Define "distance from the entrance $$$x$$$" to be the minimum number of pathways required to walk between the entrance $$$x$$$ to that room. For example, the entrance room (room $$$x$$$) has distance from the entrance $$$x$$$ as 0. Whereas the rooms connected to $$$x$$$ has distance from the entrance $$$x$$$ as 1.
| Test Group | Maximum attainable score in this group | Condition(s) |
| 1 | 3 | Every room in the maze has distance from the entrance $$$x$$$ no more than 1, and $$$N \leq 100$$$. |
| 2 | 11 | $$$N = 4$$$ and $$$x = $$$ 1. |
| 3 | 10 | The maze has the following structure:
|
| 4 | 9 | All the rooms in the maze have distance from the entrance $$$x$$$ no more than 2, and $$$N \leq 100$$$. |
| 5 | 11 | All the rooms in the maze have no more than 3 pathways directly connected to them, and $$$N \leq 1000$$$. |
| 6 | 16 | All the rooms in the maze have no more than 3 pathways directly connected to them. |
| 7 | 40 | No additional constraints. |
4 1 2 1 3 1 4 1
6
5 1 2 4 2 5 2 1 3 1
4
For example 1, the output has 6 possibilities as follows:
- 1 2 3 4
- 1 2 4 3
- 1 3 2 4
- 1 3 4 2
- 1 4 2 3
- 1 4 3 2
For example 2, the output has 4 possibilities as follows:
- 1 2 4 5 3
- 1 2 5 4 3
- 1 3 2 4 5
- 1 3 2 5 4
Recommended programming tips
If the contestant uses cin/cout, it is recommended to add 2 lines as the following:
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
"Ta-po Jewelry Co." is a factory that manufactures jewelry necklaces. The factory buys gemstones from $$$N$$$ suppliers, labeled Supplier 1 through Supplier $$$N$$$. To make a jewelry necklace, the factory chooses a piece of gemstone each from Supplier $$$l$$$ through Supplier $$$r$$$ and puts them together into a necklace in the same order as the supplier labels. However, the factory is managed by the second-generation descendant who is not very knowledgeable at jewelry despite working in the business. Even if some suppliers do not sell real gemstones, the factory still buys from them, creating necklaces of poor quality. The second-generation descendant consults Prof. TOI and receives help from a jewelry expert from the Land of Joy. The expert cuts the necklaces created by the factory so that a consecutive segment containing only real gemstones remains, in such a way that it is the longest possible consecutive segment. After necklaces from all possible supplier ranges are cut, they calculate the total length of all the necklaces.
During the whole time the expert is hired, the factory creates a necklace for each possible supplier range from $$$l$$$ to $$$r$$$ for $$$1 \leq l \leq N$$$ and $$$l \leq r \leq N$$$ and sends it to the expert to cut.
For example, the factory buys from 5 suppliers, where Supplier 1 and Supplier 4 sells fake gemstones (denoted 'F') and all other suppliers sell real gemstones (denoted 'T'). In this case, the gemstones sold by Suppliers 1 through 5 can be written as the following string: $$$$$$\tt{FTTFT}$$$$$$ and after the factory creates a necklace for each supplier range $$$l$$$ to $$$r$$$ for $$$1 \leq l \leq 5$$$ and $$$l \leq r \leq 5$$$, the following necklaces are sent to be cut by the expert:
| necklace from supplier range $$$(l,r)$$$ | necklace after the expert cuts | obtained length | necklace from supplier range $$$(l,r)$$$ | necklace after the expert cuts | obtained length | |
| F (1,1) | - | 0 | TTFT (2,5) | TT | 2 | |
| FT (1,2) | T | 1 | T (3,3) | T | 1 | |
| FTT (1,3) | TT | 2 | TF (3,4) | T | 1 | |
| FTTF (1,4) | TT | 2 | TFT (3,5) | T | 1 | |
| FTTFT (1,5) | TT | 2 | F (4,4) | - | 0 | |
| T (2,2) | T | 1 | FT (4,5) | T | 1 | |
| TT (2,3) | TT | 2 | T (5,5) | T | 1 | |
| TTF (2,4) | TT | 2 |
Thus, the factory determines that the total length of all necklaces after the expert cuts them equals to $$$0 + 1 + 2 + 2 + 2 + 1 + 2 + 2 + 2 + 1 + 1 + 1 + 0 + 1 + 1 = 19$$$
Your Task
Write an efficient program to determine the total length of all necklaces after the expert cuts them.
There are 2 lines of input:
| Line 1 | Integer $$$N$$$ denotes the number of suppliers the factory buys from, where $$$1 \leq N \leq 1,000,000$$$ |
| Line 2 | String $$$S$$$ of length $$$N$$$ whose characters are all 'T' and 'F'. Let $$$S_i$$$ denote the character at position $$$i$$$. If $$$S_i$$$ equals 'T', then Supplier $$$i$$$ sells real gemstones, but if $$$S_i$$$ equals 'F' , then Supplier $$$i$$$ sells fake gemstones ($$$i = 1, ... , N$$$). |
There is 1 line of output:
| Line 1 | The total length of all necklaces after the expert cuts them. |
Notices regarding the test sets are as follows:
| Test Group | Maximum attainable score in this group | Condition(s) |
| 1 | 6 | $$$N \leq 300$$$ |
| 2 | 18 | $$$N \leq 5{,}000$$$ |
| 3 | 6 | The string $$$S$$$ is in the format FF...FFTT...TT (the string begins with a consecutive run of character F and ends with a consecutive run of character T) |
| 4 | 7 | The string $$$S$$$ is in the format FF...FFTT...TTFF...FF (the string begins and ends with a consecutive run of character F and the string contains a consecutive run of character T as a substring in the middle) |
| 5 | 8 | The string $$$S$$$ is in the format TT...TTFF...FFTT...TT (the string begins and ends with a consecutive run of character T and the string contains a consecutive run of character F as a substring in the middle) |
| 6 | 23 | None of the substrings of string $$$S$$$ is a consecutive run of character T or a consecutive run of character F with more than 100 characters |
| 7 | 32 | No additional constraints |
5 FTTFT
19
5 TTTTT
35
8 FFFTTTTT
80
Recommended programming tips
- If the contestant uses cin/cout, it is recommended to add 2 lines as the following:
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL); - Answers may exceed the limits of the data type int