Description

故事是這個樣子的
咱們北資的大文書長思諾,是一位大電神。
他除了會畫超可愛的寒訓服和酷酷的社展服還有超級多超棒的列舉不完的作品之外,他還有一樣讓AaW驚呆的能力。

思諾:欸ㄚˊㄨˋ,你剛剛唱的湯瑪士小火車有一顆音差了3赫茲喔!
AaW:!?👀

沒錯,咱們思諾還是一位音樂神人兼音遊專業玩家,經過多年的訓練,可以精準的聽出每顆音是幾赫茲。如此的絕對音感讓AaW嚇到講不出話來。

但是,故事到這裡出現了轉折。

在經過了2023建北電資聯合寒訓 --- 確診派對之後,即便一直擁有金鐘罩的思諾還是不小心確診了。某一天,正當AaW在坐公車回家的時候,突然收到了思諾傳來了一則訊息。

阿ㄨˋ,我發現我打音遊時聽到的聲音竟然和原本的音樂差了快20赫茲欸,好痛苦喔w

原來,新冠肺炎不止會讓人發燒咳嗽,竟然還會改變聽到的聲音!
看到訊息的AaW感到十分驚訝,於是他公車又坐過站了

好不容易下了車之後,AaW下定決心要幫他的隊輔好ㄆㄚ¯ㄋㄜ˙做出一個調音器,讓他被隔離期間可以開開心心地在家中打音遊。

經過多日的研究之後,AaW成功地做出了一個調音器。這個調音器總共可以分辨 $x$ 種不同的音,並且有 $y$ 條轉移功能。每一種轉移可以透過快速傅立葉轉換搭配轉移矩陣以及大型神經網路,將 $1$ 分貝的 $a$ 音符轉成 $k$ 分貝的 $b$ 音符。

但是,因為 AaW 不會數學、不會音樂、更不會寫程式,因此這個調音器錯誤百出。不但有可能將同一顆音轉成多顆不同分貝與頻率的音,轉換的邏輯更是亂七八糟。

正在當 AaW 在煩惱該怎麼辦時,突然想到大電神 BrineTw 曾經講過一段話:

沒有什麼事情是透過一次調音器解決不了的。如果有,那就調音 $n$ 次。

真是一語驚醒夢中人!於是,AaW決定要將讓音符經過$n$層調音器再播出來。不過AaW還有一個小問題,就是他不知道他到底要用多少層調音器。因此,他決定要請你幫忙寫個程式,幫他計算經過了 $n$ 次調音之後,每個音的音量分別是多少分貝呢?

喔話說,為了避免聲音太大聲將思諾的耳朵弄壞,因此請你將音量模 $m$ 再輸出。

Input Format

第一行有四個正整數 $x \;\; y \;\; n \;\; m$
分別代表調音器能夠調幾顆音、有幾組調音關係、要將調音器套幾層以及要模的數。

接下來的 $y$ 行每行有三個正整數 $a \;\; b \;\; k$,代表經過一次的調音器,可以將每分貝的 $a$ 音轉成 $k$ 分貝的 $b$ 音。

接下來會有 $x$ 行數字,第$i$行的數字$I_i$代表第 $i$ 個音有多少分貝輸入到第一個調音器裡面($i$從$0$到$x-1$)。

$2 \le x \le 20$
$0 < y \le x ^ 2$
$0 \le a , \,b < x$
$0 \le I_i, \, k < m$
$2 \le m \le 2147483647$ 且為質數
$n$ 的範圍請看 Scoring

Output Format

請依序輸出$x$個整數,代表每顆音經過 $n$ 層調音器之後,會輸出多少分貝,並換行。(請記得模 $m$)

Sample Input 1

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

Sample Output 1

2
1
2
1

Sample Input 2

4 6 2 1013
0 1 1
1 2 2
1 3 1
2 2 5
2 3 1
3 0 2
1
0
1
2

Sample Output 2

2
4
27
6

Hints

這題其實上課簡報中有,只是不知道你們有沒有注意到w
記得看測資範圍

某人:我不會再在題敘中提及其他人
還是某人:思諾的絕對音感與 AaW 的調音器

Subtasks

No. Testdata Range Score

TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

100.0% (9/9)

Tags

Problem Source

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536
20 1000 65536 65536
21 1000 65536 65536
22 1000 65536 65536
23 1000 65536 65536
24 1000 65536 65536
25 1000 65536 65536
26 1000 65536 65536
27 1000 65536 65536
28 1000 65536 65536
29 1000 65536 65536