Gần đây nhóm của An đã khám phá ra một kho báu trên một hòn đảo hoang. Trên cánh cửa lối vào, An thấy có ghi một xâu nhị phân ~s~ (xâu chỉ chứa các chữ số ~0~ và ~1~). Ký hiệu ~|s|~ là độ dài của xâu ~s~, tức là số ký tự của xâu. Các ký tự của xâu ~s~ được đánh chỉ số từ ~1~ đến ~|s|~. Sau khi nghiên cứu các tài liệu và bản thảo cổ, An biết được mật mã để mở cửa kho bảo là một bộ ~4~ số ~l_1, r_1, l_2, r_2~ trong đó ~[l_1, r_1]~ và ~[l_2, r_2]~ là hai đoạn chữ số khác nhau của xâu ~s~. Hai đoạn này phải có cùng độ dài và dài nhất có thể, hơn nữa tổng các chữ số của hai đoạn phải bằng nhau. Cụ thể, mật mã của kho bảo là ~4~ 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 của ~s~, tức là ~l_1 \ne l_2~ hoặc ~r_1 \ne r_2~;
• ~r_1 - l_1 = r_2 - l_2~;
• ~s_{l_1} + s_{l_1 + 1}+ ... + s_{r_1} = s_{l_2} + s_{l_2 + 1} + ... + s_{r_2}~;
• ~r_1 - l_1~ lớn nhất.

Theo như An tìm hiểu được tử bản thảo, nếu có nhiều bộ số ~4~ thảo mãn thì bất kỳ bộ nào trong chúng đều có thể làm mật mã. Bây giờ An cần tìm mật mã cho kho báo, nhưng anh ấy không thể tìm được nếu không có sự giúp đỡ của bạn.

Yêu cầu

Bạn hãy giúp An tìm mật mã của kho báu.

Dữ liệu đầu vào

Gồm ~t + 1~ dòng:

• Dòng đầu tiên chứa số nguyên ~t~ ~(1 \le t \le 5)~ là số test.
• ~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)~.

Dữ liệu đầu ra

Với mỗi test in kết quả trên một dòng: nếu không tồn tại một bộ ~4~ số như vậy thì in ra ~-1~, ngược lại in ra ~4~ số ~l_1, r_1, l_2, r_2~ là mật mã cần tìm. Nếu có nhiều câu trả lời thì in ra một câu trả lời bất kì trong số chúng.

Ràng buộc dữ liệu

• Có 25% số test tương ứng với 25% số điểm thỏa mãn: Tổng độ dài tất cả các xâu ~s~ không vượt quá ~50~;
• Có 25% số test khác tương ứng với 25% số điểm thỏa mãn: Tổng độ dài tất cả các xâu ~s~ không vượt quá ~500~;
• Có 25% số test khác tương ứng với 25% số điểm thỏa mãn: Tổng độ dài tất cả các xâu ~s~ không vượt quá ~10000~;
• Có 25% số test còn lại tương ứng với 25% số điểm không có ràng buộc nào thêm.

Ví dụ

Ví dụ 1

INPUT

3
111111
010101
1

OUTPUT

1 5 2 6
1 4 2 5
-1