TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

81.2% (13/16)

Submission's AC Ratio

22.7% (25/110)

Tags

Description

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

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

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

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

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

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

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

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

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

Input Format

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

對於所有測資:

  • $ K \leq 2^ {30} $
  • $ 0 \leq A,B \leq N-1 $
  • $ P_i,C \leq 2^ {15} $
  • $ Q \leq 20 $
  • 保證不會有兩筆 $A, B$相同的紀錄

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:林翔

2021.02.14 Update: Added $\LaTeX$ by FHVirus

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 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 1
4 1000 262144 65536 1
5 1000 262144 65536 1