Sắp xếp bằng dịch vòng

Cho một mảng số nguyên $a[1\dots n]=[a_1,a_2,\dots ,a_n]$ được lưu trong một loại bộ nhớ ngoài đặc biệt.

Loại bộ nhớ này không cho phép thay đổi giá trị của một phần tử bất kỳ. Thay vào đó, nó chỉ hỗ trợ phép dịch vòng một đoạn con: bạn cắt ra một đoạn liên tiếp của mảng, dịch vòng (xoay) đoạn đó sang trái một số bước tuỳ ý, rồi đặt trở lại đúng vị trí cũ.

Cụ thể, mỗi phép dịch vòng gồm hai bước:

1. Chọn hai chỉ số $l$ và $r$ với $1\le l<r\le n$ làm hai đầu mút của đoạn.
2. Thay đoạn $a[l\dots r]$ bằng chính nó sau khi dịch vòng sang trái $d$ bước, với $1\le d\le r-l$.

Dịch vòng sang trái $d$ bước nghĩa là: dãy $[x_1,x_2,\dots ,x_m]$ trở thành $[x_{d+1},\dots ,x_m,x_1,\dots ,x_d]$. Ví dụ, $[1,4,1,3]$ là kết quả của việc dịch vòng $[3,1,4,1]$ sang trái $1$ bước, còn $[4,1,3,1]$ là kết quả của việc dịch vòng $[3,1,4,1]$ sang trái $2$ bước.

Ví dụ, nếu $a=[1,3,2,8,5]$ và bạn chọn $l=2$, $r=4$, $d=2$ thì đoạn $a[2\dots 4]=[3,2,8]$ sau khi dịch vòng sang trái $2$ bước trở thành $[8,3,2]$, và mảng trở thành $a=[1,8,3,2,5]$.

Hãy sắp xếp mảng $a$ theo thứ tự không giảm bằng không quá $n$ phép dịch vòng. Bạn không cần tìm số phép dịch nhỏ nhất: mọi cách dùng tối đa $n$ phép dịch đều được chấp nhận.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ ($1\le t\le 1000$) là số bộ dữ liệu.
• $2t$ dòng tiếp theo mô tả các bộ dữ liệu. Với mỗi bộ:
  • Dòng thứ nhất chứa số nguyên $n$ ($2\le n\le 50$) là độ dài mảng.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($-{10}^9\le a_i\le {10}^9$). Các phần tử có thể trùng nhau.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra:

• Dòng đầu chứa số nguyên $k$ ($0\le k\le n$) là số phép dịch vòng bạn sử dụng.
• $k$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $l$, $r$, $d$ mô tả một phép dịch vòng, với $1\le l<r\le n$ và $1\le d\le r-l$.

Nếu mảng đã được sắp xếp sẵn, một đáp án hợp lệ là $k=0$ và không có dòng nào theo sau. Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

• $1\le t\le 1000$
• $2\le n\le 50$
• $-{10}^9\le a_i\le {10}^9$
• $0\le k\le n$, $1\le l<r\le n$, $1\le d\le r-l$

Ví dụ