題目描述

給定 m 個區間 [L_i , R_i ] 和 n 個顔色 c_j 求下標 j 為 [L_i , R_i ] 區間内的 c_j 按序組成了多少個顔色段 cnt_i

實現細節

你需要在標準輸入（stdin）讀入樣例，並在標準輸出（stdout）輸出答案。

輸入格式

n m
L₁ R₁
L₂ R₂
...
L_m R_m
c₁ c₂ . . . c_n

輸出格式

cnt₁
cnt₂
...
cnt_m

Samples

5 2
1 4
2 5
1 1 2 2 1

2
3

提示

約束條件

• 1 ≤ n, m ≤ 200000

• 1 ≤ c_i ≤ 10⁹

• 1 ≤ L_i ≤ R_i ≤ n

子任務

1.（40 分）1 ≤ n, m ≤ 1000

2.（60 分）没有額外的約束條件

原始資料

• Zero1 題號：b515
• Hydro 題號：Z1515
• Locale：zh_TW
• Display：open