Giải bài trực tuyến

Cho bộ bài gồm n lá bài được xếp thành dãy thứ tự từ 1 tới n, đầu tiên người ta ghi vao mỗi lá bài một số nguyên là số thứ tự ban đầu của lá bài đó. Xét phép tráo S(i,m,j) : Lấy ra khỏi bộ bài m lá liên tiếp bắt đầu từ lá bài thứ i, sau đó chèn m lá bài này vào trước lá bài thứ j trong số n-m lá bài còn lại 1<=i,j<=n-m+1. Quy ước nếu j = n-m+1 thì m lá bài lấy ra sẽ được đưa vào cuối dãy

Ví dụ với n = 9

Bộ bài ban đầu : (1,2,3,4,5,6,7,8,9)

Thực hiện S(1,5,2) : (1,2,3,4,5,6,7,8,9) -> (6,1,2,3,4,5,7,8,9)

Thực hiện tiếp S(5,4,6) : (6,1,2,3,4,5,7,8,9) -> (6,1,2,3,9,4,5,7,8)

Thực hiện tiếp S(8,2,1) : (6,1,2,3,9,4,5,7,8) -> (7,8,6,1,2,3,9,4,5)

Yêu cầu : Hãy cho biết số ghi trên các lá bài sau khi thực hiện x phép tráo bài cho trước

Input

 - Dòng 1 : Chứa 2 số nguyên n và x (n,x <= 10^5)

 - x dòng tiếp theo là bộ ba số nguyên i,m,j là một phép tráo S(i,m,j)

Output

   Gồm 1 dòng duy nhất chứa n số nguyên. số thứ i là số ghi trên lá bài thứ i.

Example

Input:
9 3
1 5 2
5 4 6
8 2 1

Output:

7 8 6 1 2 3 9 4 5