Trò chơi trên lưới

Cho một lưới $4\times 4$ ban đầu trống. Bạn nhận được một dãy các quân cờ, mỗi quân có dạng $2\times 1$ (đứng) hoặc $1\times 2$ (nằm). Bạn phải lần lượt đặt tất cả các quân cờ theo đúng thứ tự trong dãy.

Khi một quân cờ được đặt, nó chiếm hai ô liền kề của lưới. Ngay sau đó, mọi ô nằm trong một hàng hoặc một cột đã bị chiếm hoàn toàn (cả 4 ô đều có quân) sẽ bị xoá. Việc xoá được thực hiện đồng thời và độc lập: ta xác định toàn bộ các hàng đầy và cột đầy trước, rồi mới xoá tất cả các ô thuộc chúng cùng lúc.

Mục tiêu của bạn là đặt được tất cả các quân cờ sao cho tại mọi thời điểm các quân cờ không bao giờ chồng lên nhau (kể cả khi đặt quân mới phải đặt vào các ô đang trống).

Với mỗi quân cờ, hãy in ra hai số nguyên dương $r,c$ — số hàng nhỏ nhất và số cột nhỏ nhất mà quân cờ đó chiếm. Cụ thể, một quân đứng đặt tại $(r,c)$ chiếm hai ô $(r,c)$ và $(r+1,c)$; một quân nằm đặt tại $(r,c)$ chiếm hai ô $(r,c)$ và $(r,c+1)$.

Dữ liệu được bảo đảm luôn tồn tại cách đặt hợp lệ. Nếu có nhiều cách, in ra một cách bất kỳ.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ gồm các ký tự 0 và 1 ($1\le |s|\le 1000$). Ký tự 0 mô tả quân đứng ($2\times 1$), ký tự 1 mô tả quân nằm ($1\times 2$).

Dữ liệu ra

In ra $|s|$ dòng — với mỗi quân cờ in hai số nguyên dương $r,c$ ($1\le r,c\le 4$) là số hàng nhỏ nhất và số cột nhỏ nhất mà quân đó chiếm.

Ràng buộc

• $1\le |s|\le 1000$
• Lưới có kích thước $4\times 4$.
• Luôn tồn tại đáp án hợp lệ.

Ví dụ