F - 駅伝中継
問題文
ストーリー
京都では毎年 1 月の第 2 日曜日に皇后盃という駅伝大会が開催されます。
駅伝大会が開催されています。
あなたは駅伝中継のために、現在の順位をリアルタイムで更新し、テレビを観ている人に伝えなければなりません。
この駅伝に参加している選手は $N$ 人です。
ゼッケン番号が $i$ の選手は現在スタート地点から $D_i$ メートル進んだところにいます。
クエリが $Q$ 個与えられるので、与えられた順番に処理してください。
クエリは次の $2$ つのいずれかです。
1 x m: ゼッケン番号 $x$ の選手が $m$ メートル進む。その後、すべての選手が $L$ メートル進む。2: クエリが与えられた時点で、スタート地点から進んだ距離が長い順に $5$ 人のゼッケン番号とスタート地点からの距離を出力する。その後、すべての選手が $L$ メートル進む。
ただし、$2$ 番目の形式のクエリが与えられるとき、すべての選手のスタート地点からの距離は異なることが保証されます。
制約
- $5 ≤ N ≤ 10^5$
- $0 ≤ d_i ≤ 10^9$
- $1 ≤ L ≤ 10^9$
- $1 ≤ Q ≤ 10^5$
- $1$ 番目の形式のクエリにおいて、$1 ≤ x ≤ N$
- $1$ 番目の形式のクエリにおいて、$1 ≤ m ≤ 10^9$
- $2$ 番目の形式のクエリが与えられるとき、すべての選手のスタート地点からの距離は異なる。
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$N \ L$
$D_1 \ D_2 \ \dots \ D_N$
$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$
ただし、$query_i$ は $i$ 個目のクエリを表しており、次の形式のいずれかで与えられる。
$1 \ x \ m$
$2$
出力
$2$ 番目の形式のクエリの回数を $q$ 回として $q×5$ 行出力してください。
$(j-1)×5 + i \ (1≤i≤5, \ 1≤j≤q)$ 行目には、$2$ 番目の形式のクエリのうち $j$ 個目のものが与えられた時点で、スタート地点から進んだ距離が長い方から $i$ 番目の選手のゼッケン番号とスタート地点からの距離をこの順に空白区切りで出力してください。
5 10
1 2 3 4 5
4
1 2 30
2
1 5 10
2
2 42
5 15
4 14
3 13
1 11
2 62
5 45
4 34
3 33
1 31
ゼッケン番号 $i$ の選手のスタート地点からの距離を $d_i$ とし、$D = (d_1, \ d_2, \ \dots, \ d_N)$ とします。
はじめ、$D = (1, \ 2, \ 3, \ 4, \ 5)$ です。
$1$ 個目のクエリでは、ゼッケン番号 $2$ の選手が $30$ メートル進みます。
その後、すべての選手が $10$ メートル進みます。
よって、$D = (11, \ 42, \ 13, \ 14, \ 15)$ となります。
$2$ 個目のクエリでは、スタート地点からの距離が長い順にゼッケン番号と距離を出力します。
その後、すべての選手が $10$ メートル進みます。
$D = (21, \ 52, \ 23, \ 24, \ 25)$ となります。
10 916316031
247319090 122300126 829427992 976937308 110636282 389294572 740241990 807080350 289712672 108533038
5
1 2 305526741
2
2
1 10 360308603
2
4 1893253339
3 1745744023
8 1723396381
7 1656558021
2 1344142898
4 2809569370
3 2662060054
8 2639712412
7 2572874052
2 2260458929
4 4642201432
3 4494692116
8 4472344474
7 4405506114
10 4134105765