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 vào 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(t,m,j)\): Lấy ra khỏi bộ bài \(m\) lá bài liên tiếp bắt đầu từ lá bài thứ \(t\), 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 với \(1 \leq t,j \leq n-m+1\). Quy ước rằng nếu \(j = n-m+1\) thì \(m\) lá bài lấy ra sẽ được đưa vào cuối dãy.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(n, k, x\) (\(n \leq 10^5, k \leq 60, x \leq 10^5\))
• \(x\) dòng tiếp theo, mỗi dòng ghi ba số nguyên \(t, m, j\) tương ứng với một phép tráo \(S(t,m,j)\)

Output

• Ghi ra một dòng chứa \(k\) số nguyên, số thứ \(i\) là số ghi trên lá bài thứ \(i\) sau khi thực hiện \(x\) phép tráo đã cho.

Example

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

7 8

Các số trên một dòng của Input/Output files được/phải ghi cách nhau ít nhất một dấu cách.