TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

96.9% (31/32)

Submission's AC Ratio

38.7% (104/269)

Tags

Description

你聽過瑞男的故事嗎?
沒有?沒關係,至少妹可聽過。

天龍國立天龍高級魔法中學是一所充滿魯蛇的魔法師學校,裡面大部分的人都非常魯,校友有很多都是天龍國有名的大法師,除了一個人例外,對,就是妹可。
妹可平常在讀書coding之餘,最喜歡做的事情就是和不同的女生出去,不管是看展覽、吃飯還是看電影。妹可平常最喜歡問別人,為什麼他沒辦法CP,卻又同時跟你說他昨天跟某個女生去了宜蘭玩之類的事。

但是就算妹可是如此的處世圓融,他還是會踢到鐵板!對,他常常被女生封鎖。有一次,他說了一個女生手指很粗,他馬上就被封鎖了。

和女生聊天真的有許多的學問,妹可自覺見識太淺薄,要達到神的境界還有一段距離,於是他決定去向神,對,就是瑞男,請教有關聊天室的問題。

瑞男,傳說瑞男的聊天室裡10個有8個是女生,甚至他曾經在一天之內已讀數十個女生,還完全沒有被封鎖,只要她們一開FB馬上就會來找瑞男聊天。
妹可馬上來到瑞男的神殿前,整理好衣冠後,雙手合十向瑞男請求:「瑞男啊瑞男,請傳授我和女生聊天的方法吧!」

這時天地異變,妹可聽到了神殿內響起了一個聲音:「這不是很簡單嗎?」
妹可的隨縱們聽完都覺得一頭霧水(妹可的隨縱都是魔法師),但是妹可突然大徹大悟!

原來,想要達到神的境界,你需要的是一些簡單的策略,我們舉個例子吧!

假設你昨天的時候,還只認識一個女生,要透過一個女生認識另外一個女生對妹可來說是很容易的,他可以再第2個小時候認識 X1 個女生,第3個小時認識 X2*X1 個女生...,也就是說,第 i 個小時有一個數字Xi,在這小時過去後妹可認識的女生會變成 Xi 倍。
然而,你要是在和女生聊天的時候,犯了一些錯誤,就會導致女生封鎖你,並且你還會得到一些仇恨值,要是仇恨值太高很顯然會影響妹可日後的人生規劃,我們假設在第 i 個小時讓一個女生封鎖你會得到 Yi 的仇恨值,妹可可以在這個小時內讓任意數量的女生封鎖他,每個人也都會增加 Yi 的仇恨值,要注意,當你被一個女生封鎖後,他當然就不會再介紹女生給你認識了。只會在那一小時結束時,女生才會介紹其他女生給你,在這之後,你可能被一些女生封鎖,然後進入下一個小時。

妹可於是計算了一下統計資料後,得出了未來一段時間的數據(每個小時的 Xi,Yi),他想知道如果他接下來又很雷的不停說女生手指怎樣怎樣,最慘的情況下會有多少仇恨值,也就是仇恨值最高會是多少。
因為統計會有很多誤差,所以妹可想要不停的修改參數來估計答案,但是每次重算太麻煩了,於是他決定交給你,妹可的魔法師隨縱,他希望你幫他寫一個魔法計算他想要的答案。

喔對了,因為你是魔法師所以可能不會理解,但是照妹可還有瑞男認識女生的速度,很快聊天室裡的女生就會超過凡人知道的數字範圍了,會累積的仇恨值也是難以估計,所以請你計算答案 MOD 109 + 7 就好。

Input Format

第一行有一個數字T,代表測資筆數。

對於每一筆測資:
第一行有一個數字N,代表總共有幾小時。
第二行有N個數字Xi,代表這一小時結束前,女生的數量會增長幾倍。
第三行有N個數字Yi,代表這一小時結束時,如果被一個女生封鎖會產生多少仇恨值。
第四行有一個數字M,代表修改數量。
接下來有M行,每行有三個數字K, P, V,分別代表修改的種類(K=1代表修改倍率,K=2代表修改仇恨值)、要修改第幾個小時以及要修改成多少。

17%,$ 1 \leq N \leq 10; M = 0; X_i,Y_i \leq 10; \prod_{i=0}^ {N-1} X_i \leq 1000 $
17%,$ 1 \leq N \leq 1000; 0 \leq M \leq 1000 $
20%,$ 1 \leq N \leq 500000; 0 \leq M \leq 100000; $ 所有更新X和X[i]都大於等於2。
23%,$ 1 \leq N \leq 500000; 0 \leq M \leq 10000 $
23%,$ 1 \leq N \leq 500000; 0 \leq M \leq 100000 $

100%,$ 1 \leq X_i,Y_i \leq 10^ 9 $

Output Format

對於每一筆測資,輸出M+1行,每行包含一個數字,代表一開始以及每次修改之後,你的答案 mod 109 + 7 的結果。

Sample Input

2
1
2
3
0
10
10 10 10 10 10 10 1 1 1 1
1 1 1 1 9 5 4 7 3 2
5
1 5 1
2 5 123456789
1 5 1
1 8 987654321
1 9 777777777

Sample Output

6
7000000
900000
678813585
678813585
294225928
75803567

Hints

假設N = 3,X = {2,1,3} Y = {3,4,1}

針對以上的資訊, 妹可如果在第1小時底被兩個女生封鎖, 他會累積最多仇恨值. 詳細過程說明如
下:
剛開始他認識1個女生.
經過第0小時,他會認識 1 * X[0] = 2 個女生.
經過第1小時, 他認識 2 * X[1] = 2 個女生.
他在第1小時底被兩個女生封鎖,總共累積 2 * Y[1] = 8 的仇恨值 .

如果妹可把 Y[1] 修改成2,那其中一種結果就會變成:
剛開始他認識 1 個女生.
經過第0小時,他認識 1 * X[0] = 2 個女生.
他在第0小時末被一個女生封鎖得到 Y[0] = 3 的仇恨值 , 並且還剩下一個女生可以聊天.
經過第1小時,他認識 1 * X[1] = 1 個女生.
經過第2小時,他認識 1 * X[2] = 3 個女生.
他在第2小時末被3個女生封鎖得到 3 * Y[2] = 3 的仇恨值,最後總共得到 6 的仇恨值.

以下是原始題目: http://olympiads.kz/ioi2015/day2/horses/zh-TW.TWN.pdf

Problem Source

IOI 2015 Day 2
Problem set by Yihda Yol
Description by 果茶

Subtasks

For Testdata: 0 ~ 0, Score: 17
For Testdata: 1 ~ 1, Score: 17
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 23
For Testdata: 4 ~ 4, Score: 23
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 524288 262144
1 3000 524288 262144
2 5000 524288 262144
3 15000 524288 262144
4 13500 524288 262144