Artifaktlar

Kostya, Yeni Babilonu axtararkən n ədəd xəritə parçası tapdı. Bu parçalar arasında a və b ədədləri ilə ifadə olunan q məhdudiyyətləri mövcuddur. Bu məhdudiyyətlər a və b parçalarının yalnız birlikdə istifadə edilə biləcəyini göstərir.

Giriş məlumatları

Birinci sətirdə n və q ədədləri verilir (1 ≤ n, q ≤ 3*10^5). Sonrakı q sətirdə məhdudiyyətlər təqdim olunur.

Çıxış məlumatları

n ədəd ədəd çıxarın; i-ci ədəd, i-ci parçanı istifadə etmək üçün tələb olunan minimum xəritə parçası sayını göstərir.

Nümunələr