Trong ca học giáo dục thể chất, thầy TICHPX chia \(2*n\) bạn sinh viên đứng thành hai hàng đối diện nhau, vị trí của các sinh viên được đánh số từ \(1\) tới \(n\) trong mỗi hàng. Một người ở vị trí \(i\) trong hàng \(1\) sẽ bắt tay với đúng một người khác ở vị trí \(i - 1, i\) hoặc \(i + 1\) trong hàng \(2\), đồng thời không ai bắt tay cùng một lúc với hai người. Trong quá trình thực hiện bài khởi động này, thầy TICHPX có thể yêu cầu một số cặp bạn đứng đối diện nhau, hoặc cặp bạn đứng liền kề nhau ở hàng \(1\) lên kiểm tra các động tác đánh cầu. Những cặp đánh cầu sau khi kiểm tra xong sẽ được ra về mà không phải xếp hàng. Các bạn còn lại do rất kính trọng thầy TICHPX nên sẽ không tự ý đi ra khỏi chỗ đứng ban đầu.

Với mỗi lần có một cặp ra khỏi hàng, đếm số cách để các bạn sinh viên còn lại ở hàng \(1\) bắt tay với các bạn ở hàng \(2\).

Đầu vào

Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^9)\), số sinh viên ban đầu ở mỗi hàng.

Dòng tiếp theo chứa số nguyên \(q\) \((1 \le q \le 2*10^5)\) là tổng số lần thầy TICHPX gọi một cặp lên kiểm tra và cho sinh viên về chỗ.

\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) và \(j\) \((1 \le i, j \le n)\) và một xâu \(s\):

• Nếu \(i = j\) thì sinh viên thứ \(i\) ở hàng thứ nhất và thứ hai rời hàng.
• Nếu \(j = i + 1\) thì sinh viên thứ \(i\) và \(i + 1\) ở hàng thứ nhất ra khỏi hàng.

Đầu vào đảm bảo luôn có đôi sinh viên ra khỏi hàng.

Đầu ra

Với mỗi lúc có cặp sinh viên ra khỏi hàng, xuất ra số cách để các bạn sinh viên còn lại bắt tay với nhau.

Subtask

\(30\%\) số test có \(q = 1, 1 \le n \le 10^6\).

\(30\%\) số test có \(q \le 1000, 1 \le n \le 10^9\).

Ví dụ

Đầu vào:

6 3
1 2
5 6
3 3

Đầu ra:

12
7
2