Câu 4 (3.0 điểm). Mật mã kho báu

Gần đây nhóm bạn An đã khám phá ra một kho báu trên hòn đảo hoang. Trên cánh cửa lối vào, An có ghi một xâu nhị phân \(s\) (xâu chỉ chứa các chữ số \(0\) và \(1\)). Kí tự \(|s|\) là độ dài của xâu \(s\), tức là số kí tự của xâu \(s\). 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áu này 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ùng độ dài và dài nhất có thể, hơn nữa tổng chữ số của hai đoạn này phải bằng nhau. Cụ thể mật mã của kho báu 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 \neq l_2\) và \(r_1 \neq r_2\)
• \(r_1 - l_1 = r_2 - l_2\)
• \(S_{l_1} + S_{l_1+1} + \dots + S_{r_1} = S_{l_2} + S_{l_2+1} + \dots + S_{r_2}\)
• \(r_2 - l_2\) lớn nhất.

Theo như An tìm hiểu được từ bản thảo nếu có nhiều bộ \(4\) thỏa 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 mật mã cho kho báu, nhưng anh ấy không thể tìm được nếu không có sự giúp đỡ của bạn. Bạn hãy giúp An tìm mật mã của kho báu.

Input

Vào từ file PASS.INP gồm:

• Dòng đầu tiên chứa số nguyên \(t\) (\(1 \le t \le 5\)) là số test.
• Mỗi dòng trong \(t\) dòng tiếp theo chứa một xâu nhị phân \(s\) (xâu \(s\) chỉ bao gồm các chữ số \(0\), \(1\) và \(1 \le |s| \le 10^6\)).

Output

Ghi ra file PASS.OUT: 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.

Example

3
111111
010101
1

1 5 2 6
1 4 2 5
-1

Scoring

• 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á \(10^4\).
• Có \(25\%\) số test còn lại ứng với \(25\%\) số điểm: không có thêm ràng buộc nào.