一片海域上有一些冰山，第 i 座冰山的體積為 Vi。 隨著氣溫的變化，冰山的體積可能增大或縮小。第 i 天，每座冰山的變化量都是 Xi。當 Xi > 0 時，所有冰山體積增加 Xi；當 Xi < 0 時，所有冰山體積減少 ? Xi；當 Xi = 0 時，所有冰山體積不變。
如果第 i 天某座冰山的體積變化后小于等于 0，則冰山會永遠消失。
冰山有大小限制 k。如果第 i 天某座冰山 j 的體積變化后 Vj 大于 k，則它會分裂成一個體積為 k 的冰山和 Vj 赗? k 座體積為 1 的冰山。第 i 天結(jié)束前（冰山增大、縮小、消失、分裂完成后），會漂來一座體積為Yi 的冰山（Yi = 0 表示沒有冰山漂來）。
小藍在連續(xù)的 m 天對這片海域進行了觀察，并準確記錄了冰山的變化。小藍想知道，每天結(jié)束時所有冰山的體積之和（包括新漂來的）是多少。 由于答案可能很大，請輸出答案除以 998244353 的余數(shù)。
輸入
輸入的第一行包含三個整數(shù) n, m, k，分別表示初始時冰山的數(shù)量、觀察的 天數(shù)以及冰山的大小限制。 第二行包含 n 個整數(shù) V1, V2, · · · , Vn，表示初始時每座冰山的體積。 接下來 m 行描述觀察的 m 天的冰山變化。其中第 i 行包含兩個整數(shù) Xi, Yi， 意義如前所述。
輸出
輸出 m 行，每行包含一個整數(shù)，分別對應每天結(jié)束時所有冰山的體積之和 除以 998244353 的余數(shù)。
樣例輸入
1 3 6
1
6 1
2 2
-1 1
樣例輸出
8
16
11
提示
【樣例說明】 在本樣例說明中，用 [a1, a2, · · · , an] 來表示每座冰山的體積。 初始時的冰山為 [1]。 第 1 天結(jié)束時，有 3 座冰山：[1, 1, 6]。 第 2 天結(jié)束時，有 6 座冰山：[1, 1, 2, 3, 3, 6]。 第 3 天結(jié)束時，有 5 座冰山：[1, 1, 2, 2, 5]。 【評測用例規(guī)模與約定】 對于 40% 的評測用例，n, m, k ≤ 2000； 對于 60% 的評測用例，n, m, k ≤ 20000； 對于所有評測用例，1 ≤ n, m ≤ 100000, 1 ≤ k ≤ 109, 1 ≤ Vi ≤ k, 0 ≤ Yi ≤ k,?? k ≤ Xi ≤ k。