第一行有兩個正整數$N,M$，分別代表參加競賽的人數與投注的人數。
接下來有$M$行，每行有兩個正整數$a_i,b_i$（$a_i\le b_i$），代表第$i$個人的投注範圍是$[a_i,b_i]$。
接下來有一行包含$N$個正整數$s_i$，代表第$i$個人在競賽中獲得的分數。

對於所有測資，$a_i,b_i\le N\le 2.5\times {10}^6;M\le 7.5\times {10}^5;s_i\le {10}^9$。

最後一個子任務為加分題。
對於該子任務，$M\le 7.5\times {10}^5$的限制不再適用。

請輸出$M$行，每行有一個正整數$T_i$，代表第$i$個人的投注範圍中最高的分數。

scanf 常用的讀入方式如下：
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。
printf 常用的輸出方式如下：
printf("%d\n",x); 輸出一行包含一個int 型態變數x。
printf("%lld\n",y); 輸出一行包含一個long long 型態變數y。
printf("%u\n",x); 輸出一行包含一個unsigned int 型態變數x。
printf("%llu\n",y); 輸出一行包含一個unsigned long long 型態變數y。

Problem Set by Yihda Yol
建國中學106學年度校隊選拔：複試pE