• Cho mảng \(a\) gồm \(n\) số nguyên dương được đánh số từ \(1\) đến \(n\). Bạn có thể thực hiện phép biến đổi dưới đây không quá \(3 * n\) lần:

• Chọn \(3\) số nguyên \(i,j\) và \(x\) (\(1\le i,j\le n;0\le x\le 10^9\)). Sau đó gán \(a_i:=a_i-x * i,a_j:=a_j+x*i\)

Hỏi: Bạn có thể tìm được một dãy biến đổi (không quá \(3 * n\) lần biến đổi) sao cho tất cả các phần tử của mảng \(a\) bằng nhau hay không ?

Input

• Dòng thứ nhất chứa số nguyên \(t(1\le t\le 10^4)\) - Số lượng testcase.

• Tiếp theo là \(t\) block, mỗi block có dạng như sau:

• Dòng thứ nhất chứa số nguyên \(n(1\le n\le 10^4)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^5)\)

  (Biết rằng: Tổng các giá trị của \(n\) ở tất cả các testcase đều không quá \(10^4\))

Output

• Ứng với mỗi testcase, câu trả lời có dạng như sau:

• Nếu không tồn tại dãy biến đổi nào thỏa mãn yêu cầu bài toán thì in ra \(-1\)

• Ngược lại, in ra số nguyên \(k(0\le k\le 3*n)\) - Thể hiện số lượng phép biến đổi trong dãy. Và \(k\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên \(i,j\) và \(x(1\le i,j\le n ; 0\le x\le 10^9)\) - Thể hiện phép biến đổi ta dùng.

  Nếu có nhiều đáp án, in ra đáp án bất kì. Chú ý rằng, bạn không nhất thiết phải giảm thiểu số \(k\).

Example

3
4
2 16 4 18
6
1 2 3 4 5 6
5
11 19 1 1 3

2
4 1 2
2 3 3
-1
4
1 2 4
2 4 5
2 3 3
4 5 1