AT_joi2026final_j.パン職人 (Baker)

JOI ベーカリーは頬が落ちるほど美味しいクロワッサンで有名なパン屋さんである． JOI ベーカリーには $ 1 $ から $ N $ までの番号が付けられた $ N $ 人のパン職人が在籍しており，職人 $ i $ ( $ 1\leqq i \leqq N $ ) は $ 1 $ つのクロワッサンを作るのに $ i $ 分かかる． $ 1 $ 人の職人が同時に複数のクロワッサンを作ることはできない．

JOI ベーカリーには今日これから， $ 1 $ から $ M $ までの番号が付けられた $ M $ 人の客が来店し，それぞれの客がクロワッサンを $ 1 $ つ注文する予定である． 今から $ t $ 分後のことを時刻 $ t $ と呼ぶことにすると，客 $ j $ ( $ 1\leqq j \leqq M $ ) がクロワッサンを注文するのは時刻 $ T_j $ である． ただし，注文後 $ L $ 分以内にクロワッサンを受け取ることのできなかった客は，諦めて店から去ってしまう． すなわち，客 $ j $ ( $ 1\leqq j \leqq M $ ) の注文に応えるには，時刻 $ T_j+L $ まで（時刻 $ T_j+L $ ちょうどを含む）にクロワッサンを作り終えなければならない．

JOI ベーカリーを管理する K 店長は，今日はちょうど $ 1 $ 人の職人を店に出勤させることを予定しており，どの職人をどの時刻に出勤させるのがよいか考えている． 職人たちは勤務中はパン作りに集中してしまうため，出勤時刻より後（出勤時刻ちょうどを含まない）に入った注文をすべて無視してしまう． すなわち，時刻 $ t $ に出勤する職人は， $ T_j > t $ を満たすような客 $ j $ ( $ 1\leqq j \leqq M $ ) の注文に応えることができない．

K 店長は現在 $ Q $ 個の出勤案を検討しており， $ q $ 番目の案 ( $ 1\leqq q \leqq Q $ ) は職人 $ A_q $ を時刻 $ B_q $ に出勤させるというものである． 検討の材料とするため， $ Q $ 個の案それぞれについて，その案を実行した際に最大で何人の客の注文に応えることができるか知りたい． なお，職人が出勤してからクロワッサンを作り始めるまでにかかる時間や，クロワッサンを $ 1 $ つ作り終えてから新しいクロワッサンを作り始めるまでにかかる時間は無視できるものとする．

JOI ベーカリーに来店する客と出勤案の情報が与えられたとき，それぞれの案において最大で何人の客の注文に応えることができるかを求めるプログラムを作成せよ．

---

入力は以下の形式で標準入力から与えられる．

$ N $ $ M $ $ L $ $ Q $ $ T_1 $ $ T_2 $ $ \cdots $ $ T_M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_Q $ $ B_Q $

標準出力に $ Q $ 行で出力せよ． $ q $ 行目 ( $ 1\leqq q \leqq Q $ ) には， $ q $ 番目の出勤案において最大で何人の客の注文に応えることができるかを表す整数を出力せよ．

---

小課題

1. ( $ 8 $ 点) $ M \leqq 10 $ ， $ Q \leqq 100,000 $ ．
2. ( $ 12 $ 点) $ M \leqq 500 $ ， $ Q \leqq 100,000 $ ．
3. ( $ 30 $ 点) $ T_M \leqq B_q < T_1+L $ ( $ 1 \leqq q \leqq Q $ )．
4. ( $ 10 $ 点) $ T_M \leqq B_q $ ( $ 1 \leqq q \leqq Q $ )．
5. ( $ 22 $ 点) $ M \leqq 500,000 $ ， $ Q \leqq 100,000 $ ．
6. ( $ 18 $ 点) 追加の制約はない．

---

Sample Explanation 1

$ 1 $ 番目の出勤案について，時刻 $ 3 $ に出勤した職人 $ 2 $ は，例えば以下のようにして $ 3 $ 人の客 $ 1,2,3 $ の注文に応えることができる．

• まず，客 $ 1 $ の注文に応えるため，時刻 $ 3 $ にクロワッサンを $ 1 $ つ作り始め， $ 2 $ 分後の時刻 $ 5 $ に作り終える．（これは，時刻 $ T_1+L=0+6=6 $ までに作り終えるという条件を満たしている．）
• 次に，客 $ 2 $ の注文に応えるため，時刻 $ 5 $ にクロワッサンを $ 1 $ つ作り始め， $ 2 $ 分後の時刻 $ 7 $ に作り終える．（これは，時刻 $ T_2+L=2+6=8 $ までに作り終えるという条件を満たしている．）
• 最後に，客 $ 3 $ の注文に応えるため，時刻 $ 7 $ にクロワッサンを $ 1 $ つ作り始め， $ 2 $ 分後の時刻 $ 9 $ に作り終える．（これは，時刻 $ T_3+L=3+6=9 $ までに作り終えるという条件を満たしている．）

客 $ 4 $ の注文は出勤時刻よりも後に入るため無視してしまい，応えることができない． よって，最大で $ 3 $ 人の客の注文に応えることができ， $ 1 $ 行目には $ 3 $ を出力する．

$ 2 $ 番目の出勤案について，時刻 $ 6 $ に出勤した職人 $ 1 $ は，例えば以下のようにして $ 2 $ 人の客 $ 2,3 $ の注文に応えることができる．

• まず，客 $ 3 $ の注文に応えるため，時刻 $ 6 $ にクロワッサンを $ 1 $ つ作り始め， $ 1 $ 分後の時刻 $ 7 $ に作り終える．（これは，時刻 $ T_3+L=3+6=9 $ までに作り終えるという条件を満たしている．）
• 次に，客 $ 2 $ の注文に応えるため，時刻 $ 7 $ にクロワッサンを $ 1 $ つ作り始め， $ 1 $ 分後の時刻 $ 8 $ に作り終える．（これは，時刻 $ T_2+L=2+6=8 $ までに作り終えるという条件を満たしている．）

客 $ 4 $ の注文は出勤時刻よりも後に入るため無視してしまい，応えることができない． また，時刻 $ 6 $ までに作り終える必要のある客 $ 1 $ の注文にも応えることができない． よって，最大で $ 2 $ 人の客の注文に応えることができ， $ 2 $ 行目には $ 2 $ を出力する．

$ 3 $ 番目の出勤案について，時刻 $ 3 $ に出勤した職人 $ 3 $ は，客 $ 1,3 $ の注文に応えることや客 $ 2,3 $ の注文に応えることはできるが， 客 $ 1,2,3 $ の注文すべてに応えることはできず，また出勤時刻よりも後に入る客 $ 4 $ の注文にも応えることができない． よって，最大で $ 2 $ 人の客の注文に応えることができ， $ 3 $ 行目には $ 2 $ を出力する．

$ 4 $ 番目の出勤案について，時刻 $ 7 $ に出勤した職人 $ 4 $ は，どの客の注文にも応えることができない． よって， $ 4 $ 行目には $ 0 $ を出力する．

この入力例は小課題 $ 1,2,5,6 $ の制約を満たす．

---

Sample Explanation 2

この入力例はすべての小課題の制約を満たす．

---

Sample Explanation 3

この入力例は小課題 $ 1,2,5,6 $ の制約を満たす．

Constraints

• $ 1 \leqq N \leqq 4\times 10^{12} $ ．
• $ 1 \leqq M \leqq 2,000,000 $ ．
• $ 1 \leqq L \leqq 2\times 10^{12} $ ．
• $ 1 \leqq Q \leqq 400,000 $ ．
• $ 0 \leqq T_j \leqq 2\times 10^{12} $ ( $ 1 \leqq j \leqq M $ )．
• $ T_j \leqq T_{j+1} $ ( $ 1 \leqq j \leqq M-1 $ )．
• $ 1 \leqq A_q \leqq N $ ( $ 1 \leqq q \leqq Q $ )．
• $ 0 \leqq B_q \leqq 4\times 10^{12} $ ( $ 1 \leqq q \leqq Q $ )．
• 入力される値はすべて整数である．