You are given a 4x4 grid. You play a game — there is a sequence of tiles, each of them is either 2x1 or 1x2. Your task is to consequently place all tiles from the given sequence in the grid. When tile is placed, each cell which is located in fully occupied row or column is deleted (cells are deleted at the same time independently). You can place tile in the grid at any position, the only condition is that tiles (and tile parts) should not overlap. Your goal is to proceed all given figures and avoid crossing at any time.

Input

The only line contains a string s consisting of zeroes and ones (1 ≤ |s| ≤ 1000). Zero describes vertical tile, one describes horizontal tile.

Output

Output |s| lines — for each tile you should output two positive integers r,c, not exceeding 4, representing numbers of smallest row and column intersecting with it.

If there exist multiple solutions, print any of them.

Example

Input


010


Output


1 1
1 2
1 4

Note

Following image illustrates the example after placing all three tiles: 

<image> Then the first row is deleted:  <image>

Difficulty: MEDIUM
Tags: Implementation

Constructive algorithms

Starter code:

Solutions:
b = [['3 4', '1 4'], ['1 1', '1 3']]
o = [0, 0]
for i in map(int, input()):
	print(b[i][o[i] % 2])
	o[i] += 1


mp = [0, 0, 0, 0]
s = input()
for i in s:
	if i == '0':
		if mp[0] < 1:
			print(3, 1)
			mp[0] = 1
		else:
			print(1, 1)
			mp[0] = 0
	elif mp[2] < 1:
		print(1, 3)
		mp[2] = 1
	else:
		print(1, 1)
		mp[2] = 0


p = [0, 0]
for d in input():
	c = int(d)
	print(p[c] + 1, c * 2 + 1)
	p[c] = (p[c] + 2 - c) % 4


mod = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
l = [[0] * 4 for i in range(4)]
s = si()
hor = [[1, 2], [2, 2], [3, 2], [4, 2]]
ver = [[1, 1], [3, 1]]
(o, z) = (0, 0)
for i in s:
	if i == '1':
		print(*hor[o % 4])
		o += 1
	else:
		print(*ver[z % 2])
		z += 1


from sys import stdin, stdout
from math import gcd, sqrt
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
N = 10 ** 6 + 7
v = 1
h = 0
for i in S():
	if i == '0':
		print(v % 4, 1)
		v += 2
	else:
		print(h % 4 + 1, 3)
		h += 1


lastv = 1
lasth = 1
for c in input():
	if c == '0':
		print(lastv, 1)
		lastv ^= 2
	else:
		print(lasth, 3)
		lasth = 1 if lasth == 4 else lasth + 1


import sys, math
from collections import deque, defaultdict
import operator as op
from functools import reduce
I = sys.stdin.readline

def ii():
	return int(I().strip())

def li():
	return list(map(int, I().strip().split()))

def mi():
	return map(int, I().strip().split())

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def valid(row, col, rows, cols, rcross, lcross):
	return rows[row] == 0 and cols[col] == 0 and (rcross[col + row] == 0) and (lcross[col - row] == 0)

def div(n):
	tmp = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				n = n // i
				cnt += 1
			tmp.append((i, cnt))
	if n > 1:
		tmp.append((n, 1))
	return tmp

def isPrime(n):
	if n <= 1:
		return False
	elif n <= 2:
		return True
	else:
		flag = True
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				flag = False
				break
		return flag

def s(b):
	cnt = 0
	while b > 0:
		tmp = b % 10
		cnt += tmp
		b = b // 10
	return cnt

def main():
	ans = ''
	col = [(1, 1), (3, 1)]
	row = [(1, 2), (2, 2), (3, 2), (4, 2)]
	ans = []
	s = I().strip()
	cntC = 0
	cntR = 0
	for i in s:
		if i == '0':
			ans.append(col[cntC % 2])
			cntC += 1
		else:
			ans.append(row[cntR % 4])
			cntR += 1
	for i in ans:
		print(*i)
main()


s = input()
r = 0
c = 0
for i in s:
	if i == '0' and r == 0:
		print(1, 1)
		r = 1
	elif i == '0' and r == 1:
		print(3, 1)
		r = 0
	elif i == '1' and c == 0:
		print(4, 3)
		c = 1
	else:
		print(4, 1)
		c = 0


from collections import defaultdict, deque
import sys
import bisect
input = sys.stdin.readline
s = [int(i) for i in input() if i != '\n']
(hor, ver) = (0, 0)
for i in range(len(s)):
	if s[i] == 1:
		if hor == 0:
			print(1, 1)
			hor += 1
		elif hor == 1:
			print(1, 3)
			hor += 1
		else:
			print(1, 1)
			hor = 1
	if s[i] == 0:
		if ver == 0:
			print(2, 1)
			ver += 1
		elif ver == 1:
			print(2, 2)
			ver += 1
		elif ver == 2:
			print(2, 3)
			ver += 1
		elif ver == 3:
			print(2, 4)
			ver += 1
		else:
			print(2, 1)
			ver = 1


s = input()
a = False
b = False
for ch in s:
	if ch == '0':
		print(3 if a else 1, 1)
		a = not a
	else:
		print(4, 1 if b else 3)
		b = not b


l = list(input())
flag1 = 0
flag2 = 0
for i in range(len(l)):
	if l[i] == '0':
		if flag1 == 0:
			print(1, 4)
			flag1 = 1
		else:
			print(3, 4)
			flag1 = 0
	else:
		print(flag2 % 4 + 1, 1)
		flag2 += 1


s = input()
zero = [(1, 3), (3, 3), (1, 4), (3, 4)]
one = [(1, 1), (2, 1), (3, 1), (4, 1)]
h = 0
v = 0
for i in s:
	if i == '0':
		print(*zero[v])
		v += 1
	else:
		print(*one[h])
		h += 1
	h %= 4
	v %= 4


s = input()
a = [[0] * 4 for i in range(4)]
for k in range(len(s)):
	isk = int(s[k])
	if isk == 0:
		for i in range(4):
			if a[2][i] == 0:
				print(3, i + 1)
				a[2][i] = 1
				a[3][i] = 1
				break
	elif a[0][0] == 0:
		a[0][0] = 1
		a[0][1] = 1
		print(1, 1)
	else:
		a[0][2] = 1
		a[0][3] = 1
		print(1, 3)
	for i in range(4):
		if sum(a[i]) == 4:
			a[i] = [0] * 4
	for j in range(4):
		if a[0][j] + a[1][j] + a[2][j] + a[3][j] == 4:
			a[0][j] = 0
			a[1][j] = 0
			a[2][j] = 0
			a[3][j] = 0


s = input()
hor = 0
vert = 0
for i in range(len(s)):
	if s[i] == '0':
		if vert == 1:
			vert = 0
			print('3 1')
		else:
			vert = 1
			print('1 1')
	else:
		hor += 1
		print(hor, 2)
		hor %= 4


s = input()
a = b = 0
for i in s:
	if i == '0':
		print(a + 1, 3)
		a = (a + 2) % 4
	else:
		print(b + 1, 1)
		b = (b + 1) % 4


s = input().strip()
hor = False
ver = False
for i in s:
	if i == '0':
		if ver:
			print('1 1')
			ver = False
		else:
			print('3 1')
			ver = True
	elif i == '1':
		if hor:
			print('1 1')
			hor = False
		else:
			print('1 3')
			hor = True


s = list(input())
(hor, ver) = (False, False)
for i in s:
	if i == '0':
		if not ver:
			print(3, 1)
			ver = True
		else:
			print(1, 1)
			ver = False
	elif not hor:
		print(1, 3)
		hor = True
	else:
		print(1, 1)
		hor = False


s = input()
has_h = False
has_v = False
for c in s:
	if c == '0':
		if has_v:
			print(1, 4)
		else:
			print(3, 4)
		has_v = not has_v
	else:
		if has_h:
			print(1, 3)
		else:
			print(1, 1)
		has_h = not has_h


__author__ = 'Esfandiar'
s = input()
Len = len(s)
f = ff = 0
for i in range(Len):
	if s[i] == '0':
		if f == 0:
			print(1, 1)
			f = 1
		else:
			print(3, 1)
			f = 0
	elif ff == 0:
		print(4, 3)
		ff = 1
	else:
		print(4, 1)
		ff = 0


a = [['3 4', '1 4'], ['1 1', '1 3']]
p = [0, 0]
for d in map(int, input()):
	print(a[d][p[d] % 2])
	p[d] += 1


import os
import sys
import math
import heapq
from decimal import *
from io import BytesIO, IOBase
from collections import defaultdict, deque

def r():
	return int(input())

def rm():
	return map(int, input().split())

def rl():
	return list(map(int, input().split()))
s = input()
n = len(s)
zero = False
one = False
for i in range(n):
	if s[i] == '0':
		if zero:
			print(3, 1)
		else:
			print(1, 1)
		zero = not zero
	else:
		if one:
			print(4, 1)
		else:
			print(4, 3)
		one = not one


s = input()
print(*('%d %d' % ((1, s[:i].count('0') % 4 + 1) if s[i] == '0' else (3, s[:i].count('1') % 2 * 2 + 1)) for i in range(len(s))), sep='\n')


s = input()
(v1, h1) = (-1, -1)
for i in range(len(s)):
	if s[i] == '0':
		if v1 == -1:
			print(1, 1)
			v1 = 1
		else:
			print(3, 1)
			v1 = -1
	elif h1 == -1:
		print(4, 3)
		h1 = 1
	else:
		print(4, 1)
		h1 = -1


s = input()
i = 0
j = 0
k = 0
while i < len(s):
	if s[i] == '0':
		if j == 0:
			print('1 1')
			j = 1
		else:
			print('3 1')
			j = 0
	elif k == 0:
		print('4 3')
		k = 1
	else:
		print('4 1')
		k = 0
	i += 1


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	import numpy

	def dprint(*args, **kwargs):
		print(*args, file=sys.stderr)
	dprint('debug mode')
except Exception:

	def dprint(*args, **kwargs):
		pass
inId = 0
outId = 0
if inId > 0:
	dprint('use input', inId)
	try:
		f = open('input' + str(inId) + '.txt', 'r')
		sys.stdin = f
	except Exception:
		dprint('invalid input file')
if outId > 0:
	dprint('use output', outId)
	try:
		f = open('stdout' + str(outId) + '.txt', 'w')
		sys.stdout = f
	except Exception:
		dprint('invalid output file')
	atexit.register(lambda : sys.stdout.close())
s = input()
c0 = 0
c1 = 1
for x in s:
	if x == '0':
		c0 = c0 % 4
		c0 += 1
		print(1, c0)
	else:
		c1 = 4 - c1
		print(3, c1)


(v, h) = (0, 0)
for x in input():
	if x == '0':
		print(v + 1, 1)
		v = (v + 2) % 4
	else:
		print(h + 1, 2)
		h = (h + 1) % 4


s = input()
_r11 = False
_r43 = False
for x in s:
	if x == '0' and _r11:
		print(3, 1)
		_r11 = False
	elif x == '0' and (not _r11):
		print(1, 1)
		_r11 = True
	elif x == '1' and _r43:
		print(4, 1)
		_r43 = False
	elif x == '1' and (not _r43):
		print(4, 3)
		_r43 = True


s = input()
twos = 0
fours = 0
for i in s:
	if i == '0':
		if twos == 1:
			print(3, 1)
			twos = 0
		else:
			print(1, 1)
			twos = 1
	else:
		print(fours + 1, 2)
		fours += 1
		fours %= 4


import heapq
s = input()
heap = []
a = False
b = False
for c in s:
	if c == '0':
		if not a:
			print('1 1')
			a = True
		else:
			print('3 1')
			a = False
	elif not b:
		print('4 3')
		b = True
	else:
		print('4 1')
		b = False


s = input()
(zero, one) = (0, 0)
for si in s:
	if si == '0':
		print(1, zero % 4 + 1)
		zero += 1
	else:
		print(4, one % 2 * 2 + 1)
		one += 1


s = input()
_ = [False, False]
for i in range(len(s)):
	if s[i] == '0':
		if _[1]:
			print(3, 1)
			_[1] = False
		else:
			print(1, 1)
			_[1] = True
	elif _[0]:
		print(4, 1)
		_[0] = False
	else:
		print(4, 3)
		_[0] = True


pos = (((1, 1), (3, 1)), ((4, 3), (4, 1)))
cnt = [0, 0]
for t in map(int, input()):
	print(*pos[t][cnt[t]])
	cnt[t] = 1 - cnt[t]


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions
from collections import deque, defaultdict, OrderedDict
from fractions import Fraction
from decimal import Decimal

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	for i in range(1):
		s = rs()
		z = 0
		o = 0
		for i in range(len(s)):
			if s[i] == '0':
				z += 1
				if z > 4:
					z = 1
				print(3, z)
			if s[i] == '1':
				o += 1
				if o > 2:
					o = 1
				if o == 1:
					print(1, 1)
				else:
					print(1, 3)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import os, sys
from io import BytesIO, IOBase

def main():
	s = input().strip()
	vert = 0
	hor = 0
	for i in s:
		if i == '0':
			print(2 * vert + 1, 1)
			vert ^= 1
		else:
			print(hor + 1, 2)
			hor = (hor + 1) % 4
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


s = input()
horizontal = -1
vertical = -1
v = []
h = []
for i in range(len(s)):
	if s[i] == '0':
		vertical += 1
		vertical %= 2
		if vertical == 0:
			ans = 1
		else:
			ans = 3
		print(ans, 1)
	else:
		horizontal += 1
		horizontal %= 4
		print(horizontal + 1, 2)


a = [int(x) for x in list(input())]
zero = [0]
one = [-1]
ans = []
for v in a:
	if v == 0:
		zero.append(zero[-1] + 1)
		ans.append([1, zero[-1]])
		if zero[-1] == 4:
			zero = [0]
	else:
		one.append(one[-1] + 2)
		ans.append([3, one[-1]])
		if one[-1] == 3:
			one = [-1]
for value in ans:
	print(*value)


Ahr = [1, 1, 4, 4]
Ahc = [1, 3, 1, 3]
Avr = [2, 2, 2, 2]
Avc = [1, 2, 3, 4]
s = input()
v = s.count('0')
h = s.count('1')
vc = 0
hc = 0
for char in s:
	if char == '0':
		print(Avr[vc % 4], Avc[vc % 4])
		vc += 1
	else:
		print(Ahr[hc % 4], Ahc[hc % 4])
		hc += 1


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
s = inp()
a = 1
b = 1
for i in s:
	if i == '0':
		print(1, a)
		a += 1
	else:
		print(3, b)
		b += 2
	a = (a - 1) % 4 + 1
	b = (b - 1) % 4 + 1


s = input()
v = 0
h = 0
for c in s:
	if c == '0':
		v += 1
		print(1, v)
		v = v % 4
	elif c == '1':
		h += 1
		print(3, h * 2 - 1)
		h = h % 2


s = list(input())
countzero = 1
countone = 1
for j in range(len(s)):
	if s[j] == '0':
		print(3, countzero)
		countzero += 1
		if countzero == 5:
			countzero = 1
	else:
		print(1, countone)
		countone += 2
		if countone == 5:
			countone = 1


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def myceil(x, y):
	return (x + y - 1) // y

def clearGridCol(grid):
	for i in range(4):
		sm = 0
		for j in range(4):
			sm += grid[j][i]
		if sm == 4:
			for j in range(4):
				grid[j][i] = 0

def clearGridRow(grid):
	for i in range(4):
		sm = 0
		for j in range(4):
			sm += grid[i][j]
		if sm == 4:
			for j in range(4):
				grid[i][j] = 0

def Solution():
	s = get_string()
	cnt0 = 0
	cnt1 = 0
	for c in s:
		if c == '0':
			if cnt0 == 0:
				print(1, 1)
				cnt0 += 1
			elif cnt0 == 1:
				print(3, 1)
				cnt0 += 1
			if cnt0 == 2:
				cnt0 = 0
		else:
			if cnt1 == 0:
				print(4, 3)
				cnt1 += 1
			elif cnt1 == 1:
				print(4, 1)
				cnt1 += 1
			if cnt1 == 2:
				cnt1 = 0

def main():
	Solution()
main()