Županijsko natjecanje iz informatike 2018. / Prva podskupina (1. i 2. razred) - 3. zadatak

U Wonkinoj tvornici čokolade glavna je atrakcija brzi vrtuljak uz koji se nalazi čokoladna prskalica. Dok se vrtuljak okreće, svake sekunde jedna osoba na vrtuljku prođe pokraj prskalice koja je tada poprska čokoladom.

U jednoj od današnjih vožnji na vrtuljku sudjelovalo je \(N\) djece, označenih brojevima od \(1\) do \(N\) redom kojim su sjedili na vrtuljku. Vožnja je trajala \(M\) sekundi. U sekundi \(1\) pokraj prskalice je prošlo dijete \(1\), u sljedećoj sekundi dijete \(2\), i tako dalje do djeteta \(N\), nakon čega je u sekundi \(N + 1\) ponovno dijete \(1\) prošlo pokraj prskalice, i tako dalje redom, u krug.

Prskalica je, nažalost, bila pokvarena i u nekim vremenskim intervalima nije prskala čokoladu pa su se djeca žalila upravitelju tvornice. Sakupljeno je \(K\) izjava sljedećeg oblika: „od sekunde \(A\) do sekunde \(B\) (uključivo) prskalica nije radila“. Napišite program koji, uz pretpostavku da su izjave istinite, za svako od \(N\) djece s vrtuljka određuje koliko je najviše puta to dijete moglo biti poprskano čokoladom tijekom vožnje na vrtuljku.

Ulazni podaci

U prvom retku nalaze se prirodni brojevi \(N\) \((2 \leq N \leq 100 000)\) i \(M\) \((2 \leq M \leq 10^{16})\), broj djece na vrtuljku i duljina vožnje u sekundama.

U drugom retku nalazi se se prirodan broj \(K\) \((1 \leq K \leq 100 000)\), broj izjava.

U svakom od sljedećih K redaka nalaze se brojevi \(A\) i \(B\) \((1 \leq A \leq B \leq M)\) koji znače da između sekundi \(A\) i \(B\) (uključujući i te sekunde) prskalica nije radila.

Izlazni podaci

Za svako dijete od \(1\) do \(N\) u zaseban redak ispišite traženi najveći mogući broj čokoladnih prskanja.

Primjeri test podataka

Ulaz

3 10
2
1 2
4 10

Izlaz

0
0
1

Pojašnjenje

Prskalica nije radila u \(1\). i \(2\). sekundi, kao ni od \(4\). do \(10\). sekunde. Pretpostavimo li da je prskalica radila u \(3\). sekundi, dijete \(3\) moglo je tada biti poprskano. Ostalo dvoje djece nije moglo biti poprskano čokoladom.

Ulaz

5 20
3
3 6
10 14
13 18

Izlaz

1
2
1
2
1

Ulaz

10 100
2
30 50
25 62

Izlaz

6
6
7
7
6
6
6
6
6
6