Mật mã kho báu

Cho một xâu nhị phân \(s\) chỉ gồm các ký tự \(0\) và \(1\). Các ký tự trong xâu được đánh số từ \(1\) đến \(|s|\).

Một mật mã mở cửa kho báu là một bộ bốn số \(l_1, r_1, l_2, r_2\) sao cho:

• \(1 \le l_1 \le r_1 \le |s|\) và \(1 \le l_2 \le r_2 \le |s|\);
• \([l_1, r_1]\) và \([l_2, r_2]\) là hai đoạn khác nhau;
• hai đoạn có cùng độ dài lớn nhất có thể;
• tổng các chữ số trên hai đoạn bằng nhau, tức là $$ s_{l_1} + s_{l_1+1} + … + s_{r_1} = s_{l_2} + s_{l_2+1} + … + s_{r_2}. $$

Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Yêu cầu. Với mỗi test, hãy tìm một mật mã kho báu. Nếu không tồn tại thì in ra \(-1\).

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1 \le t \le 5\)).
• \(t\) dòng tiếp theo, mỗi dòng chứa một xâu nhị phân \(s\) (\(1 \le |s| \le 10^6\)).

Tổng độ dài tất cả các xâu không vượt quá \(10^6\).

Output

Với mỗi test:

• nếu không tồn tại đáp án, in ra \(-1\);
• ngược lại, in ra bốn số \(l_1, r_1, l_2, r_2\).

Input

%
3
111111
010101
1

Output

%
1 5 2 6
2 5 3 6
-1

Scoring

• (25%) Tổng độ dài tất cả các xâu không vượt quá \(50\).
• (25%) Tổng độ dài tất cả các xâu không vượt quá \(500\).
• (25%) Tổng độ dài tất cả các xâu không vượt quá \(10^4\).
• (25%) Không có ràng buộc gì thêm.