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 đó \(\lbrack l_{1},r_{1}\rbrack\) và \(\lbrack l_{2},r_{2}\rbrack\) 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 \leq l_{1} \leq r_{1} \leq |s|\) và \(1 \leq l_{2} \leq r_{2} \leq |s|\)

• \(\lbrack l_{1},r_{1}\rbrack\) và \(\lbrack l_{2},r_{2}\rbrack\) là hai đoạn khác nhau của \(s\), tức là \(l_{1}
  eq l_{2}\) hoặc \(r_{1}
  eq r_{2}\);

• \(r_{1} - l_{1} = r_{2} - l_{2}\);

• \(s_{l_{1}} + s_{l_{1} + 1} + \ldots + s_{r_{1}} = s_{l_{2}} + s_{l_{2} + 1} + \ldots + 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ộ bà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. Bạn hãy giúp An tìm mật mã của kho báu.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên \(t\ (1 \leq t \leq 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 \leq |s| \leq 10^{6}\))

Kết quả:

+ Với mỗi test in kết quả trên 1 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.

Ví dụ:

Ràng buộc:

+ 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.