你知道GATE嗎?知道為什麼GATE世界裡有這麼多的種族嗎?
不知道沒關係,有個相貌老態內心與聲音卻像是個小蘿莉的的老婆婆會告訴你。
精靈的創世神話,是從他們的祖先一男一女被神明指引至『原始之森』開始,分散在大陸各地的各個精靈部落也都流傳著類似的故事,當詢問它們『原是之森』的位置時,北方的精靈指向南方、南方的精靈指向北方,所有的精靈部落都指向同一個方向,而那個地方在現在被稱之為『阿爾努斯』,其實不僅僅是精靈族,其實矮人族、地精族、小人族⋯⋯所有的種族的故鄉都在『阿爾努斯』。
而他們是從『阿爾努斯』的哪裡冒出來的呢?
(欲知詳情請待下回分曉(誤
其實他們都是在『GATE』開啟的時候移居過來的,每隔數百年、甚至上千年,寂靜就會被打破,『GATE』再次開啟,每次都會有新的住人到訪這個世界,他們與其他種族交戰或是融入,在這個世界落地生根,而『GATE』再度陷入沉寂,直到下一次開啟,這就是這個世界不斷重複發展而來的歷史。
假設這個世界秩序與倫理道德都是正常的(不會重婚、亂倫、亂生、亂來⋯⋯亂七八糟)。
自衛隊的二等陸衛——『伊丹』,現在知道每個部落有多少人,並且知道他們出生的比例,以及搬遷的情況,為了維持多樣性,他們每個部落都有一個共同特別的習性,就是他們的小孩會在春天出生,當他們的小孩出生半年後都會被送往別的部落。
而這裡的神怕會有太多人造成部落過度壅擠、破壞生態,因此只要有一個部落超過 $10 ^ 9 + 7$ 人時 就會被滅村,使其部落人數少於 $10 ^ 9 + 7$,而神一次殺的人數一定是 $10 ^ 9 + 7$ 的倍數。
假設他們出生後一年就能孕育新的子孫,『伊丹』現在想知道 $K$ 年後每個部落會有多少人。
噢對了,如果記錄中顯示一個部落會把小孩送給自己部落,那麼這筆記錄就是偽造的,你可以不必理會。
對於每筆輸入
第一行會有正整數 $N$ 表示這個世界有多少的部落($ 2 \leq N \leq 100 $)。
第二行有 $N$ 個數字,$P_i$ 表示現在各個部落有多少人。
第三行有一個正整數 $M$ ,
接下來 $M$ 行,每行有三個數字 $A, B, C$,代表 $A$ 部落在每年的一半時,會將原本人口 $C$ 倍的小孩送到 $B$ 部落。
接下來會有一個正整數 $Q$,表示有 $Q$ 筆詢問。
接下來的 $Q$ 行,每行有一個正整數 $K$,表示詢問 $K$ 年後的部落人數狀況。
對於所有測資:
針對每筆詢問,輸出一行以空白隔開的 $N$ 個數字,代表 $K$ 年後,每個部落各有多少人。
第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。
依此類推。
Gate:林翔
2021.02.14 Update: Added $\LaTeX$ by FHVirus
No. | Testdata Range | Score |
---|---|---|
1 | 0~5 | 100 |