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