某工程公司設計了一個自動分裝的系統。貨物會一個一個的被送進此系統，經過一些切換器的轉送後，會被輸送到 \(n\) 個貨箱。 系統有 \(n - 1\) 個切換器與 \(n\) 個貨箱。每個切換器有一個入口以及左右兩個出口，切換器的出口會接到其他切換器或是連接到貨箱，貨箱則只有入口。

下圖是一個 \(n = 7\) 的例子：

圓代表切換器，方形代表貨箱。請注意編號 \(1 \sim n - 1\) 的裝置是切換器，而貨箱的編號為 \(n \sim 2n - 1\)。
貨物的入口一定是 \(1\) 號切換器的入口。每一個切換器會分別記錄左右兩個出口所通往貨箱的總重量。當貨物進入切換器時，切換器會將貨物轉送到貨箱總重量較輕的那個出口。
如果兩邊一樣重，則送往左邊。貨物進入貨箱後就存放在該貨箱，並將該貨物的重量加入貨箱的總重，因此可能影響下一個貨物的運送路徑。

輸入格式

第一行包含兩個正整數 \(n\) 和 \(m\)，其中 \(n \leq 10^5\) 且 \(m \leq 100\)。
第二行有 \(n\) 個非負整數，依序表示編號為 \(n \sim 2n - 1\) 的貨箱初始重量。
第三行包含 \(m\) 個正整數，代表接下來依序進入的貨物重量。全部貨箱初始的重量與貨物重量總和不會超過 \(10^9\)。
從第四行開始有 \(n - 1\) 行，這些行描述系統架構的資訊。每一行包含三個整數 \(p, s, t\)，代表裝置 \(p\) 的左右出口分別接到裝置 \(s\) 與 \(t\)，其中 \(p\) 一定是切換器的編號 (\(1 \leq p < n\))。

同一行中的數字之間以空白間隔。

輸出格式

輸出一行有 \( m \) 個整數，依序代表接下來進入系統的 \( m \) 個貨物所進入到的貨箱編號，數字之間以一個空白間隔。

範例輸入 1

4 5
0 0 0 0
5 3 4 2 1
1 2 3
2 4 5
3 6 7

範例輸出 1

4 6 7 5 5

範例輸入 2

7 2
9 2 1 6 8 7 5
2 3
1 2 5
2 3 7
3 13 10
4 11 9
6 12 8
5 6 4

範例輸出 2

8 7

提示

以上圖的例子來說，假設每一個貨箱目前的重量如各矩形下方的標示，下 一個到達的貨物的運送過程如下:
一號切換器左邊出口是連到 {13, 10, 7} 三個貨箱，目前總重5+6+9=20;
右邊出口連到的是 {12, 8, 11, 9} 四個貨箱，目 前總重 7+2+8+1=18，因此貨物會由右邊出口送到 5 號切換器。
5 號切換器的左邊與 右邊的貨箱總重是一樣的(7+2=8+1)，因此貨物由左出口送至 6 號切換器。
最後， 6 號切換器將貨物送到 8 號貨箱(7>2)。貨物進入貨箱後就存放在該貨箱，
該貨物 的重量就會加入該貨箱的總重，因此可能影響下一個貨物的運送路徑。