AtCoder Grand Contest 047 - Product Simulation

This is an output-only problem. You shouldn't read anything from the input.

In short, your task is to simulate multiplication by using only comparison (x < y) and addition (x + y). There is no input in this problem, you just print a sequence of operations.

Imagine that there is a big array a[0], a[1], ..., a[N-1] of length N. The first two values are initially two non-negative integers A and B (which are unknown to you), the other elements are zeros. Your goal is to get the product A \cdot B in a[2] at the end.

You are allowed operations of two types, with the following format (where 0 \leq i, j, k < N):

* `+ i j k` — applies operation a[k] = a[i] + a[j].
* `< i j k` — applies operation a[k] = a[i] < a[j]. That is, if a[i] < a[j] then a[k] becomes 1, otherwise it becomes 0.



You can use at most Q operations. Elements of a can't exceed V. Indices (i, j, k) don't have to be distinct. It's allowed to modify any element of the array (including the first two). The actual checker simulates the process for multiple pairs (A, B) within a single test. Each time, the checker chooses values A and B, creates the array a = [A, B, 0, 0, \ldots, 0], applies all your operations and ensures that a[2] = A \cdot B.

Constraints

* 0 \leq A, B \leq 10^9
* N = Q = 200\,000
* V = 10^{19} = 10\,000\,000\,000\,000\,000\,000

Input

The Standard Input is empty.

Output

In the first line, print the number of operations. Each operation should then be printed in a single line of format `+ i j k` or `< i j k`.

Example

Input




Output

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
n = 97
p = print
r = range

def a(i, j, k, l=0):
	p(chr(43 + l * 17), i, j, k)

def b(i):
	a(i, i, i + 1)

def d(x, i, j):
	for t in r(30):
		b(j + t - 1)
		a(j + t, n, j + t)
		for s in r(j + t, j + 29):
			b(s)
		a(j + 29, x, i + t, 1)
		b(j + t - 1)
		a(j + t, i + t, j + t)
p(3933)
a(0, 1, n)
a(2, n, n, 1)
a(0, n, 3)
a(1, n, 4)
d(3, 5, 36)
d(4, 36, 67)
for t in r(59):
	a(2, 2, 2)
	for s in r(t + 1):
		if t - 30 < s < 30:
			a(5 + t - s, 36 + s, 98)
			a(n, 98, 99, 1)
			a(2, 99, 2)


class CodeGen:
	codes = []
	cnt = 100

	def __init__(self, A, B):
		self.A = A
		self.B = B
		self.C1 = self.one()
		self.C2 = self.pow2(self.C1, 1)
		self.C3 = self.pow2(self.C1, 2)
		self.C4 = self.pow2(self.C1, 3)
		self.POW2 = [self.C1]
		for i in range(32):
			self.POW2.append(self.pow2(self.C1, i + 1))

	def allocate(self):
		self.cnt += 1
		return self.cnt - 1

	def plus(self, x, y):
		l = self.allocate()
		self.codes.append(f'+ {x} {y} {l}')
		return l

	def gt(self, x, y):
		l = self.allocate()
		self.codes.append(f'< {x} {y} {l}')
		return l

	def ge(self, x, y):
		return self.gt(x, self.plus(y, self.C1))

	def pow2(self, x, n):
		t = x
		for _ in range(n):
			t = self.plus(t, t)
		return t

	def one(self):
		return self.gt(self.allocate(), self.plus(self.A, self.B))

	def bits(self, x, n):
		result = []
		t = self.allocate()
		for i in range(n - 1, -1, -1):
			bit = self.ge(self.plus(self.POW2[i], t), x)
			result.append(bit)
			t = self.plus(t, self.pow2(bit, i))
		return result

	def mult(self, x, y):
		return self.gt(self.C1, self.plus(x, y))

	def show(self, ans):
		t = self.allocate()
		self.codes.append(f'+ {ans} {t} 2')
		print(len(self.codes))
		for c in self.codes:
			print(c)

	def pluss(self, xs):
		if len(xs) == 1:
			return xs[0]
		return self.plus(xs[0], self.pluss(xs[1:]))

class Eval(CodeGen):

	def __init__(self, A, B):
		super().__init__(A, B)

	def allocate(self):
		return 0

	def plus(self, x, y):
		return x + y

	def gt(self, x, y):
		if x < y:
			return 1
		return 0

	def show(self, ans):
		print(ans)
gen = CodeGen(0, 1)
A = gen.bits(gen.A, 32)
B = gen.bits(gen.B, 32)
X = []
for _ in range(64):
	X.append(gen.allocate())
for i in range(32):
	for j in range(32):
		X[i + j] = gen.plus(X[i + j], gen.mult(A[i], B[j]))
ans = gen.allocate()
for i in range(64):
	ans = gen.plus(ans, gen.pow2(X[i], 62 - i))
gen.show(ans)


n = q = 2 * 10 ** 5
fla = []

def pri(s):
	fla.append(s)
pri('+ 0 1 5')
pri('< 3 5 4')
max_log = 30
pri('+ 0 4 0')
pri('+ 1 4 1')
for i in reversed(range(max_log)):
	pri('+ 3 4 8')
	for _ in range(i):
		pri('+ 8 8 8')
	pri('+ 6 8 9')
	pri('< 9 0 %d' % (100 + i))
	pri('+ %d 3 9' % (100 + i))
	for _ in range(i):
		pri('+ 9 9 9')
	pri('+ 6 9 6')
for i in reversed(range(max_log)):
	pri('+ 3 4 8')
	for _ in range(i):
		pri('+ 8 8 8')
	pri('+ 7 8 9')
	pri('< 9 1 %d' % (200 + i))
	pri('+ %d 3 9' % (200 + i))
	for _ in range(i):
		pri('+ 9 9 9')
	pri('+ 7 9 7')

def an(i, j, k):
	pri('+ %d %d 6' % (i, j))
	pri('< %d %d 7' % (i, j))
	pri('< %d %d 8' % (j, i))
	pri('+ 7 8 7')
	pri('< 7 6 %d' % k)
for i in range(max_log):
	for j in range(max_log):
		an(100 + i, 200 + j, 6)
		pri('+ %d 6 %d' % (i + j + 300, i + j + 300))
for i in range(max_log * 2):
	for _ in range(i):
		pri('+ %d %d %d' % (300 + i, 300 + i, 300 + i))
	pri('+ %d 2 2' % (300 + i))
print(len(fla))
print('\n'.join(fla))


n = 97

def c(i, j, k):
	print('<', i, j, k)

def a(i, j, k):
	print('+', i, j, k)

def d(x, i, j):
	for t in range(30):
		a(j + t - 1, j + t - 1, j + t)
		a(j + t, n, j + t)
		for s in range(j + t, j + 29):
			a(s, s, s + 1)
		c(j + 29, x, i + t)
		a(j + t - 1, j + t - 1, j + t)
		a(j + t, i + t, j + t)
print(3933)
a(0, 1, n)
c(2, n, n)
a(0, n, 3)
a(1, n, 4)
d(3, 5, 36)
d(4, 36, 67)
for t in range(59):
	a(2, 2, 2)
	for s in range(t + 1):
		if t - 30 < s < 30:
			a(5 + t - s, 36 + s, 98)
			c(n, 98, 99)
			a(2, 99, 2)


n = 97
r = range
L = '<'
P = '+'
l = [3933, P, 0, 1, n, L, 2, n, n, P, 0, n, 3, P, 1, n, 4]
a = lambda i, j: [P, i, j, i]
b = lambda i: [P, i, i, i + 1]

def d(x, i, j):
	return sum([sum([b(j + t - 1), a(j + t, n), *(b(s) for s in r(j + t, j + 29)), [L, j + 29, x, i + t], b(j + t - 1), a(j + t, i + t)], []) for t in r(30)], [])
l += d(3, 5, 36)
l += d(4, 36, 67)
for t in r(59):
	l += a(2, 2)
	for s in r(t + 1):
		if t - 30 < s < 30:
			l += [P, 5 + t - s, 36 + s, 98]
			l += [L, n, 98, 99]
			l += a(2, 99)
print(*l)


p = '+'
h = '<'
ans = []

def f(a, b, c, d):
	ans.append([a, b, c, d])
f(p, 0, 1, 3)
f(h, 2, 3, 3)
f(p, 2, 3, 10)
f(p, 2, 3, 100)
for i in range(29):
	f(p, 10 + i, 10 + i, 11 + i)
	f(p, 100 + i, 100 + i, 101 + i)
for i in range(29, -1, -1):
	f(p, 8, 10 + i, 9)
	f(h, 0, 9, 10 + i)
	f(h, 10 + i, 3, 9)
	f(p, 98, 100 + i, 99)
	f(h, 1, 99, 100 + i)
	f(h, 100 + i, 3, 99)
	f(h, 100 + i, 3, 100 + i)
	for j in range(i):
		f(p, 9, 9, 9)
		f(p, 99, 99, 99)
	f(p, 8, 9, 8)
	f(p, 98, 99, 98)
for i in range(30):
	f(h, 4, 4, 4)
	for j in range(30):
		f(h, 10 + i, 100 + j, 5)
		for k in range(j):
			f(p, 5, 5, 5)
		f(p, 4, 5, 4)
	for k in range(i):
		f(p, 4, 4, 4)
	f(p, 2, 4, 2)
print(len(ans))
for i in ans:
	print(*i)