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
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);
