TopCoder

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

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

36.0% (9/25)

Tags

Description

你知道GATE嗎?知道為什麼GATE世界裡有這麼多的種族嗎?
不知道沒關係,有個相貌老態內心與聲音卻像是個小蘿莉的的老婆婆會告訴你。

精靈的創世神話,是從他們的祖先一男一女被神明指引至『原始之森』開始,分散在大陸各地的各個精靈部落也都流傳著類似的故事,當詢問它們『原是之森』的位置時,北方的精靈指向南方、南方的精靈指向北方,所有的精靈部落都指向同一個方向,而那個地方在現在被稱之為『阿爾努斯』,其實不僅僅是精靈族,其實矮人族、地精族、小人族......所有的種族的故鄉都在『阿爾努斯』。

而他們是從『阿爾努斯』的哪裡冒出來的呢?
(欲知詳情請待下回分曉(誤

其實他們都是在『GATE』開啟的時候移居過來的,每隔數百年、甚至上千年,寂靜就會被打破,『GATE』再次開啟,每次都會有新的住人到訪這個世界,他們與其他種族交戰或是融入,在這個世界落地生根,而『GATE』再度陷入沉寂,直到下一次開啟,這就是這個世界不斷重複發展而來的歷史。

假設這個世界秩序與倫理道德都是正常的(不會重婚、亂倫、亂生、亂來.....亂七八糟)。

自衛隊的二等陸衛—『伊丹』,現在知道每個部落有多少人,並且知道他們出生的比例,以及搬遷的情況,為了維持多樣性,他們每個部落都有一個共同特別的習性,就是他們的小孩會在春天出生,當他們的小孩出生半年後都會被送往別的部落。

而這裡的神怕會有太多人造成部落過度壅擠、破壞生態,因此只要有一個部落超過 1e9 + 7 人時 就會被滅村,使其部落人數少於1e9 + 7 ,而神一次殺的人數一定是1e9 + 7 的倍數。

假設他們出生後一年就能孕育新的子孫,『伊丹』現在想知道 K 年後每個部落會有多少人。

噢對了,如果記錄中顯示一個部落會把小孩送給自己部落,那麼這筆記錄就是偽造的,你可以不必理會。

Input Format

對於每筆輸入
第一行會有正整數 N 表示這個世界有多少的部落( $ 2 \leq N \leq 100 $ )。
第二行有 N 個數字,Pi表示現在各個部落有多少人。
第三行有一個正整數 M ,
接下來 M 行,每行有三個數字A、B、C,代表A部落在每年的一半時,會將原本人口C倍的小孩送到B部落。
接下來會有一個正整數 Q 表示有 Q 筆詢問。
接下來的 Q 行,每行有一個正整數 K 表示詢問 K 年後的部落人數狀況。

$ K \leq 2^ {30} ; 0 \leq A,B \leq N-1 ; Pi,C \leq 2^ {15} $

Output Format

針對每筆詢問,輸出一行以空白隔開的N個數字,代表K年後,每個部落各有多少人。

Sample Input

3
1 2 3
4
0 1 3
1 0 2
2 0 2
2 1 2
4
1
2
3
4

Sample Output

11 11 3
39 50 3
145 173 3
497 614 3

Hints

第1年部落0會增加 2*2 + 3*2 = 10個人,部落1會增加 1*3 + 3*2 = 9個人,部落2不會增加人數,所以第1年人數分別是 11 11 3。
第2年部落0會增加 11*2 + 3*2 = 28個人,部落1會增加 11*3 + 3*2 = 39個人,部落2不會增加人數,所以第2年人數分別是 39 50 3。
依此類推。

Problem Source

Gate:林翔

Subtasks

No. Testdata Range Score
1 0~5 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1