Anda memperoleh sebuah permainan video yang dirilis oleh perusahaan JOI. Permainan itu dibuat dengan cukup baik, dan Anda memainkannya setiap hari dengan cukup senang.

Suatu hari, muncul sebuah level yang disebut “Laser” oleh para pemain. Tampaknya level itu sangat sulit, bahkan pemain hebat sekalipun hanya memiliki peluang sangat kecil untuk menyelesaikannya. Setelah berkali-kali mencobanya, Anda menyadari bahwa level itu mungkin dapat diselesaikan dengan mengambil keputusan sangat cepat, sehingga Anda berpikir untuk menanganinya dengan membuat program.

Level Laser berlangsung di tempat yang memiliki $N$ dinding pelindung. Area permainan berbentuk persegi panjang dan dibagi menjadi petak persegi berukuran $1\times1$. Setiap petak dinyatakan sebagai $(x,y)$ dengan bilangan bulat tak negatif $x,y$. Petak $(0,0)$ berada di sudut kiri bawah, sedangkan $(x,y)$ adalah petak yang berada $x$ petak ke kanan dan $y$ petak ke atas dari $(0,0)$.

Saat level dimulai, musuh muncul dan menyerang. Sebanyak $M$ serangan dilakukan secara berurutan. Pada serangan ke-$j$, musuh menembakkan laser lurus dari petak $(P_j,N+1)$ menuju petak $(P_j,0)$.

Setiap dinding menempati beberapa petak berurutan dengan koordinat $y$ yang sama. Dinding $i$ ($1 \le i \le N$) berbentuk persegi panjang dengan lebar horizontal $B_i-A_i+1$ dan tinggi $1$, serta pada awal level menempati petak $(A_i,i)$ sampai $(B_i,i)$. Anda boleh menggeser dinding ke kiri atau kanan berapa kali pun tepat sebelum serangan pertama dan di antara dua serangan. Dalam satu gerakan, Anda dapat menggeser satu dinding satu petak ke kanan atau satu petak ke kiri.

Kekuatan laser melemah saat mengenai dinding. Anda ingin meminimalkan kekuatannya dengan menggeser dinding sehingga laser mengenai semua dinding.

Dalam level ini, Anda ingin membuat jumlah gerakan dinding sesedikit mungkin.

Tugas

Diberikan posisi awal setiap dinding dan posisi setiap serangan musuh. Tentukan jumlah gerakan minimum untuk masing-masing dinding saat dinding digeser sehingga setiap laser mengenai semua dinding.

Masukan

Baca data berikut dari masukan standar.

• Baris pertama berisi dua bilangan bulat $N,M$ yang dipisahkan spasi. Artinya, terdapat $N$ dinding pada level ini dan musuh melakukan $M$ serangan.
• Baris ke-$i$ ($1 \le i \le N$) dari $N$ baris berikutnya berisi dua bilangan bulat $A_i,B_i$ yang dipisahkan spasi. Artinya, pada awal level dinding $i$ menempati petak $(A_i,i)$ sampai $(B_i,i)$.
• Baris ke-$j$ ($1 \le j \le M$) dari $M$ baris berikutnya berisi bilangan bulat $P_j$. Artinya, pada serangan ke-$j$, musuh menembakkan laser lurus dari petak $(P_j,N+1)$ menuju petak $(P_j,0)$.

Keluaran

Tuliskan $N$ baris ke keluaran standar. Pada baris ke-$i$ ($1 \le i \le N$), tuliskan jumlah gerakan minimum untuk dinding $i$.

Batasan

Semua data masukan memenuhi kondisi berikut.

• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $0 \le A_i \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $0 \le P_j \le 1\,000\,000\,000$ ($1 \le j \le M$).

Subsoal

Subsoal 1 [10 poin]

• Memenuhi $N=1$.

Subsoal 2 [45 poin]

• Memenuhi $A_i=0$ ($1 \le i \le N$).

Subsoal 3 [45 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

4 4
0 3
4 4
2 7
8 11
6
4
3
8

Keluaran 1

5
10
1
7

Penjelasan

Untuk masukan ini, salah satu cara menggeser dinding yang meminimalkan jumlah gerakan adalah sebagai berikut:

• Sebelum serangan pertama, geser dinding $1$ ke kanan 3 kali, dinding $2$ ke kanan 2 kali, jangan geser dinding $3$, dan geser dinding $4$ ke kiri 2 kali.
• Sebelum serangan kedua, jangan geser dinding $1$, geser dinding $2$ ke kiri 2 kali, jangan geser dinding $3$, dan geser dinding $4$ ke kiri 2 kali.
• Sebelum serangan ketiga, jangan geser dinding $1$, geser dinding $2$ ke kiri 1 kali, jangan geser dinding $3$, dan geser dinding $4$ ke kiri 1 kali.
• Sebelum serangan keempat, geser dinding $1$ ke kanan 2 kali, dinding $2$ ke kanan 5 kali, dinding $3$ ke kanan 1 kali, dan dinding $4$ ke kanan 2 kali.

Dengan cara ini, dinding $1$ digeser 5 kali, dinding $2$ sebanyak 10 kali, dinding $3$ sebanyak 1 kali, dan dinding $4$ sebanyak 7 kali.

Awal level; serangan pertama; serangan kedua; serangan ketiga; serangan keempat.

Masukan 2

7 11
12 39
22 23
5 38
6 47
10 43
0 50
18 46
38
19
15
1
12
29
29
0
6
40
6

Keluaran 2

34
178
13
6
18
0
36