Tablica

Ο Ivo έχει έναν πίνακα ~N \times N~. Ο πίνακας έχει τους ακέραιους αριθμούς ~1~ έως ~N^2~ εγγεγραμμένους με τάξη μείζονος σειράς (row-major order). Οι ακόλουθες λειτουργίες μπορούν να γίνουν στον πίνακα:

1. Περιστροφή σειράς – όλα τα κελιά σε μια γραμμή περιστρέφονται δεξιά, έτσι ώστε ο αριθμός στην τελευταία στήλη μετακινείται στην πρώτη.
2. Περιστροφή στήλης – όλα τα κελιά μιας στήλης περιστρέφονται προς τα κάτω, έτσι ώστε ο αριθμός στην τελευταία σειρά μετακινείται στην πρώτη.

Ο Ivo αισθάνεται περιστασιακά την επιθυμία να μετακινήσει έναν αριθμό ~X~ στο κελί ~(R, C)~ και προχωρά ως εξής:

• Όσο το ~X~ δεν βρίσκεται στη στήλη ~C~, περιστρέψτε τη σειρά στην οποία βρίσκεται.
• Όσο το ~X~ δεν βρίσκεται στη σειρά ~R~, περιστρέψτε τη στήλη στην οποία βρίσκεται.

Ακολουθεί ένα παράδειγμα του τρόπου μετακίνησης του αριθμού ~6~ στο κελί ~(3,\,4)~, ξεκινώντας από την αρχική διαμόρφωση:

Ο Ivo θέλει να μετακινήσει ~K~ αριθμούς τον ένα μετά τον άλλο. Γράψτε ένα πρόγραμμα που να υπολογίζει τον αριθμό των απαιτούμενων περιστροφών.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~N~ ~(2 \le N \le 10\,000)~ και ~K~ ~(1 \le K \le 1\,000)~, τη διάσταση του πίνακα και τον αριθμό των κινήσεων.

Κάθε μία από τις επόμενες ~K~ γραμμές περιέχει τρεις ακέραιους αριθμούς ~X~ ~(1 \le X \le N^2)~, ~R~ και ~C~ ~(1 \le R, C \le N)~, η περιγραφή μίας κίνησης που θέλει να κάνει ο Ivo. Ο Ivo κάνει τις κινήσεις με τη σειρά που δίνονται.

Έξοδος

Τυπώστε ~K~ γραμμές · για κάθε κίνηση, τυπώστε τον αριθμό των περιστροφών που απαιτούνται.

Παραδείγματα

input

4 1
6 3 4

output

3

input

4 2
6 3 4
6 2 2

output

3
5

input

5 3
1 2 2
2 2 2
12 5 5

output

2
5
3