Petya learned a new programming language CALPAS. A program in this language always takes one non-negative integer and returns one non-negative integer as well.

In the language, there are only three commands: apply a bitwise operation AND, OR or XOR with a given constant to the current integer. A program can contain an arbitrary sequence of these operations with arbitrary constants from 0 to 1023. When the program is run, all operations are applied (in the given order) to the argument and in the end the result integer is returned.

Petya wrote a program in this language, but it turned out to be too long. Write a program in CALPAS that does the same thing as the Petya's program, and consists of no more than 5 lines. Your program should return the same integer as Petya's program for all arguments from 0 to 1023.

Input

The first line contains an integer n (1 ≤ n ≤ 5·105) — the number of lines.

Next n lines contain commands. A command consists of a character that represents the operation ("&", "|" or "^" for AND, OR or XOR respectively), and the constant xi 0 ≤ xi ≤ 1023.

Output

Output an integer k (0 ≤ k ≤ 5) — the length of your program.

Next k lines must contain commands in the same format as in the input.

Examples

Input

3
| 3
^ 2
| 1


Output

2
| 3
^ 2


Input

3
&amp; 1
&amp; 3
&amp; 5


Output

1
&amp; 1


Input

3
^ 1
^ 2
^ 3


Output

0

Note

You can read about bitwise operations in <https://en.wikipedia.org/wiki/Bitwise_operation>.

Second sample:

Let x be an input of the Petya's program. It's output is ((x&1)&3)&5 = x&(1&3&5) = x&1. So these two programs always give the same outputs.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Constructive algorithms


Solutions:
n = int(input())
(a, b) = (1023, 0)
for _ in range(n):
	(c, d) = input().split()
	d = int(d)
	if c == '|':
		(a, b) = (a | d, b | d)
	elif c == '&':
		(a, b) = (a & d, b & d)
	elif c == '^':
		(a, b) = (a ^ d, b ^ d)
print('2\n| {}\n^ {}'.format(a ^ b ^ 1023, a ^ 1023))


def execute(prg, n):
	for (op, x) in prg:
		if op == '|':
			n |= x
		elif op == '&':
			n &= x
		elif op == '^':
			n ^= x
	return n
n = int(input())
prg = []
for i in range(n):
	(op, x) = map(str, input().split())
	x = int(x)
	prg.append((op, x))
zeroes = execute(prg, 0)
ones = execute(prg, 1023)
(orx, andx, xorx) = (0, 0, 0)
for i in range(10):
	bit = 1 << i
	if zeroes & bit == 0 and ones & bit == 0:
		pass
	elif zeroes & bit == 0 and ones & bit != 0:
		andx |= bit
	elif zeroes & bit != 0 and ones & bit == 0:
		xorx |= bit
		andx |= bit
	elif zeroes & bit != 0 and ones & bit != 0:
		orx |= bit
		andx |= bit
print(3)
print('|', orx)
print('&', andx)
print('^', xorx)


(a, b) = (0, 1023)
for i in range(int(input())):
	cmd = input()
	(c, x) = cmd.split()
	x = int(x)
	if c == '|':
		(a, b) = (a | x, b | x)
	elif c == '&':
		(a, b) = (a & x, b & x)
	else:
		(a, b) = (a ^ x, b ^ x)
x = 0
y = 1023
z = 0
for i in range(10):
	a_i = a >> i & 1
	b_i = b >> i & 1
	if a_i and b_i:
		x |= 1 << i
	if not a_i and (not b_i):
		y ^= 1 << i
	if a_i and (not b_i):
		z ^= 1 << i
print('3\n| {}\n& {}\n^ {}'.format(x, y, z))


n = int(input())
bits0 = [0] * 10
bits1 = [1] * 10
b0 = 0
b1 = 1023
fname = ['&', '|', '^']
f = [[[0, 0], [0, 1]], [[0, 1], [1, 1]], [[0, 1], [1, 0]]]
for i in range(n):
	s = input()
	e = str(bin(int(s[2:])))
	d = int(s[2:])
	if s[0] == '^':
		b0 = b0 ^ d
		b1 = b1 ^ d
	elif s[0] == '|':
		b0 = b0 | d
		b1 = b1 | d
	elif s[0] == '&':
		b0 = b0 & d
		b1 = b1 & d
for j in range(10):
	bits0[9 - j] = b0 % 2
	b0 = b0 // 2
	bits1[9 - j] = b1 % 2
	b1 = b1 // 2
c = [[0] * 10, [0] * 10, [1] * 10]
for j in range(10):
	if bits0[j] == bits1[j]:
		if bits0[j] == 0:
			c[2][j] = 0
		else:
			c[1][j] = 1
	elif bits0[j] == 1:
		c[0][j] = 1
print(3)
(c0, c1, c2) = [0, 0, 0]
for i in range(10):
	c0 += c[0][i] * 2 ** (9 - i)
	c1 += c[1][i] * 2 ** (9 - i)
	c2 += c[2][i] * 2 ** (9 - i)
print('^ ' + str(c0))
print('| ' + str(c1))
print('& ' + str(c2))


from math import *
n = int(input())
x = 0
y = 1023
for i in range(n):
	gg = input().split()
	if gg[0] == '&':
		x &= int(gg[1])
		y &= int(gg[1])
	if gg[0] == '|':
		x |= int(gg[1])
		y |= int(gg[1])
	if gg[0] == '^':
		x ^= int(gg[1])
		y ^= int(gg[1])
print(3)
print('|', x & y)
print('&', x | y)
print('^', x & (y ^ 1023))


import sys
import io, os
input = sys.stdin.readline
n = int(input())
X = [-1] * 10
for i in range(n):
	(c, x) = map(str, input().split())
	x = int(x)
	if c == '&':
		for j in range(10):
			if not x & 1 << j:
				X[j] = 0
	elif c == '|':
		for j in range(10):
			if x & 1 << j:
				X[j] = 1
	else:
		for j in range(10):
			if x & 1 << j:
				if X[j] == -1:
					X[j] = 2
				elif X[j] == 2:
					X[j] = -1
				elif X[j] == 1:
					X[j] = 0
				else:
					X[j] = 1
(a, b, c) = (0, 0, 0)
for i in range(10):
	if X[i] == -1:
		a |= 1 << i
	elif X[i] == 2:
		a |= 1 << i
		c |= 1 << i
	elif X[i] == 1:
		b |= 1 << i
print(3)
print('&', a)
print('|', b)
print('^', c)


import queue

def readTuple():
	return input().split()

def readInts():
	return tuple(map(int, readTuple()))

def to_int(x):
	x = x[::-1]
	res = 0
	for i in x:
		res <<= 1
		res |= i
	return res

def solve():
	res = ['X'] * 10
	(n,) = readInts()
	(a, b) = (0, 1023)
	for _ in range(n):
		(char, num) = readTuple()
		num = int(num)
		if char == '|':
			a |= num
			b |= num
		if char == '&':
			a &= num
			b &= num
		if char == '^':
			a ^= num
			b ^= num
	(XOR, OR) = ([], [])
	for i in range(10):
		b1 = a & 1 << i
		b2 = b & 1 << i
		if b1 and b2:
			OR.append(1)
			XOR.append(0)
		if not b1 and (not b2):
			OR.append(1)
			XOR.append(1)
		if b1 and (not b2):
			OR.append(0)
			XOR.append(1)
		if not b1 and b2:
			OR.append(0)
			XOR.append(0)
	print(2)
	print(f'| {to_int(OR)}')
	print(f'^ {to_int(XOR)}')
solve()


n = int(input())
a = 0
b = 1023
for i in range(n):
	(s, d) = input().split()
	d = int(d)
	if s == '|':
		a |= d
		b |= d
	elif s == '&':
		a &= d
		b &= d
	elif s == '^':
		a ^= d
		b ^= d
ans = []
ans.append(('|', 1023 ^ a ^ b))
ans.append(('^', 1023 ^ b))
print(len(ans))
for i in range(len(ans)):
	print(ans[i][0] + ' ' + str(ans[i][1]))


z = 0
o = 1023
n = int(input())
for i in range(n):
	(a, b) = input().split()
	b = int(b)
	if a == '&':
		z = z & b
		o = o & b
	if a == '^':
		z = z ^ b
		o = o ^ b
	if a == '|':
		z = z | b
		o = o | b
z = '{:010b}'.format(z)
o = '{:010b}'.format(o)
an = 0
r = 0
xo = 0
pw = 512
for i in range(10):
	an += pw
	if o[i] == '0' and z[i] == '0':
		an -= pw
	if o[i] == '1' and z[i] == '1':
		r += pw
	if o[i] == '0' and z[i] == '1':
		xo += pw
	pw //= 2
print(3)
print('&', an)
print('|', r)
print('^', xo)


import sys
input = sys.stdin.readline
n = int(input())
start1 = 0
start2 = 1023
for _ in range(n):
	(a, b) = map(str, input().split())
	b = int(b)
	if a == '|':
		start1 = b | start1
		start2 = b | start2
	elif a == '^':
		start1 = b ^ start1
		start2 = b ^ start2
	else:
		start1 = b & start1
		start2 = b & start2
ans = []
ands = 1023
xors = 0
ors = 0
for i in range(10):
	k = 1 << i
	if start1 & k and start2 & k:
		ors += k
	elif start1 & k and (not start2 & k):
		xors += k
	elif not start1 & k and (not start2 & k):
		ands -= k
print(3)
print('&', ands)
print('^', xors)
print('|', ors)


n = int(input())
queries = list((input().split() for _ in range(n)))
(a, b) = (0, (1 << 10) - 1)
for (c, x) in queries:
	x = int(x)
	if c == '|':
		(a, b) = (a | x, b | x)
	elif c == '&':
		(a, b) = (a & x, b & x)
	elif c == '^':
		(a, b) = (a ^ x, b ^ x)
(x, y, z) = (0, (1 << 10) - 1, 0)
for i in range(10):
	a_i = a >> i & 1
	b_i = b >> i & 1
	if a_i and b_i:
		x |= 1 << i
	if not a_i and (not b_i):
		y ^= 1 << i
	if a_i and (not b_i):
		z ^= 1 << i
print(3)
print('|', x)
print('&', y)
print('^', z)


def fun(n1, o, n2):
	if o == '|':
		return n1 | n2
	elif o == '&':
		return n1 & n2
	else:
		return n1 ^ n2

def fun2(n):
	l = [0 for i in range(10)]
	for i in range(9, -1, -1):
		if 1 << i <= n:
			l[i] = 1
			n -= 1 << i
	return l
n = int(input())
a = 0
b = 1023
for i in range(n):
	(o, n2) = input().split()
	n2 = int(n2)
	a = fun(a, o, n2)
	b = fun(b, o, n2)
l1 = fun2(a)
l2 = fun2(b)
a = 0
b = 0
for i in range(10):
	if l1[i] == 1 and l2[i] == 1:
		a += 1 << i
	elif l1[i] == 0 and l2[i] == 0:
		a += 1 << i
		b += 1 << i
	elif l1[i] == 1 and l2[i] == 0:
		b += 1 << i
print(2)
print('|', a)
print('^', b)


n = int(input())
m = 2 ** 10 - 1
a = 0
b = m
for _ in range(n):
	(op, l) = input().split()
	v = int(l)
	if op == '|':
		a |= v
		b |= v
	elif op == '&':
		a &= v
		b &= v
	else:
		a ^= v
		b ^= v
print(3)
print('&', a | b)
print('|', a & b)
print('^', a & (b ^ m))


from operator import and_, or_, xor
n = int(input())
ops = []
for _ in range(n):
	s = input().split()
	ops.append([s[0], int(s[1])])
samples = [0, 1023]
ans = []
tab = {'^': xor, '&': and_, '|': or_}
for s in samples:
	for op in ops:
		s = tab[op[0]](s, op[1])
	ans.append(s)
(diz, con, xxor) = ('', '', '')
for (b1, b2) in zip('{0:0>10b}'.format(ans[0]), '{0:0>10b}'.format(ans[1])):
	if b1 == '1' and b2 == '0':
		diz += '0'
		con += '1'
		xxor += '1'
	elif b1 == '0' and b2 == '1':
		diz += '0'
		con += '1'
		xxor += '0'
	elif b1 == '1' and b2 == '1':
		diz += '1'
		con += '1'
		xxor += '0'
	elif b1 == '0' and b2 == '0':
		diz += '0'
		con += '0'
		xxor += '0'
print(3)
print('|', int(diz, 2))
print('&', int(con, 2))
print('^', int(xxor, 2))


import sys
import math
import collections
import heapq
n = int(input())
(a, b) = (1023, 0)
for i in range(n):
	(x, y) = (i for i in input().split())
	y = int(y)
	if x == '&':
		a &= y
		b &= y
	elif x == '|':
		a |= y
		b |= y
	else:
		a ^= y
		b ^= y
print(2)
print('|', a ^ b ^ 1023)
print('^', a ^ 1023)


from collections import defaultdict as dd
from collections import Counter as ccd
from itertools import permutations as pp
from itertools import combinations as cc
from random import randint as rd
from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq as hq
import math
mod = pow(10, 9) + 7

def inp(flag=0):
	if flag == 0:
		return list(map(int, input().strip().split(' ')))
	else:
		return int(input())
n = int(input())
a = 0
b = 1023
for i in range(n):
	(c, k) = input().strip().split(' ')
	k = int(k)
	if c == '|':
		a |= k
		b |= k
	elif c == '^':
		a ^= k
		b ^= k
	elif c == '&':
		a &= k
		b &= k
OR = 0
XOR = 0
for i in range(10):
	x = 1 << i
	if a & x and b & x:
		OR |= x
	if a & x and ~b & x:
		XOR |= x
	if ~a & x and ~b & x:
		OR |= x
		XOR |= x
print('2')
print('|', OR)
print('^', XOR)


n = int(input())
A = 1023
B = 0
a = 1023
b = 0
print(4)
for i in range(n):
	s = str(input())
	if s[0] == '&':
		a = a & int(s[2:])
		b = b & int(s[2:])
	elif s[0] == '|':
		a = a | int(s[2:])
		b = b | int(s[2:])
	elif s[0] == '^':
		a = a ^ int(s[2:])
		b = b ^ int(s[2:])
Al = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Bl = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
al = [0 for kk in range(10)]
bl = [0 for kk in range(10)]
for i in range(9, -1, -1):
	if a >= 2 ** i:
		al[i] = 1
		a -= 2 ** i
for i in range(9, -1, -1):
	if b >= 2 ** i:
		bl[i] = 1
		b -= 2 ** i
And = []
Or = []
Xor = []
for i in range(10):
	if al[i] == 0 and bl[i] == 0:
		And.append(i)
	if al[i] == 0 and bl[i] == 1:
		Xor.append(i)
	if al[i] == 1 and bl[i] == 1:
		Or.append(i)
r = 0
for i in range(10):
	if i not in And:
		r += 2 ** i
print('&', r)
r = 0
if Xor == []:
	print('^ 0')
	print('^ 0')
elif Xor == [0]:
	print('^ 0')
	print('& 1')
else:
	r = 2 ** (max(Xor) + 1) - 1
	print('^', r)
	r = 0
	for i in range(max(Xor) + 1):
		if i not in Xor:
			r += 2 ** i
	print('^', r)
r = 0
for i in range(10):
	if i in Or:
		r += 2 ** i
print('|', r)


import sys
input = sys.stdin.readline
from bisect import bisect_left
from bisect import bisect_right
from math import ceil, factorial

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
n = int(input())
ops = []
for _ in range(n):
	ops.append(input().split())
first = 0
last = 1023
for i in ops:
	if i[0] == '|':
		first = first | int(i[1])
		last = last | int(i[1])
	elif i[0] == '&':
		first = first & int(i[1])
		last = last & int(i[1])
	else:
		first = first ^ int(i[1])
		last = last ^ int(i[1])
a = bin(first).replace('0b', '')
b = bin(last).replace('0b', '')
a = '0' * (10 - len(a)) + a
b = '0' * (10 - len(b)) + b
a = list(map(int, list(a)))
b = list(map(int, list(b)))
_xor = []
_and = []
_or = []
for i in range(10):
	if a[i] == b[i]:
		if a[i] == 0:
			_xor.append(1)
			_and.append(0)
			_or.append(0)
		else:
			_xor.append(1)
			_and.append(1)
			_or.append(1)
	elif a[i] == 1:
		_xor.append(1)
		_and.append(1)
		_or.append(0)
	else:
		_xor.append(0)
		_and.append(1)
		_or.append(0)
x = y = z = 0
for i in range(10):
	x += _xor[i] * 2 ** (9 - i)
	y += _and[i] * 2 ** (9 - i)
	z += _or[i] * 2 ** (9 - i)
print(3)
print('^ ', x)
print('& ', y)
print('| ', z)


q = int(input())

def calc(f):
	ret1 = 0
	ret2 = 1023
	for op in f:
		if op[0] == '&':
			ret1 &= op[1]
			ret2 &= op[1]
		elif op[0] == '|':
			ret1 |= op[1]
			ret2 |= op[1]
		elif op[0] == '^':
			ret1 ^= op[1]
			ret2 ^= op[1]
	return (ret1, ret2)
f = list()
for i in range(q):
	(oper, n) = input().split()
	n = int(n)
	f.append((oper, n))
(op0, op1) = calc(f)
op0 = ('0000000000' + bin(op0)[2:])[-10:][::-1]
op1 = ('0000000000' + bin(op1)[2:])[-10:][::-1]
o = 0
x = 0
for i in range(10):
	if op0[i] == '1' and op1[i] == '1':
		o += 2 ** i
	elif op0[i] == '1' and op1[i] == '0':
		x += 2 ** i
	elif op0[i] == '0' and op1[i] == '0':
		o += 2 ** i
		x += 2 ** i
print(2)
print('| ' + str(o))
print('^ ' + str(x))


n = int(input())
mask_ans1 = 1023
mask_ans2 = 0
for i in range(n):
	(com, x) = input().split()
	x = int(x)
	if com == '&':
		mask_ans1 &= x
		mask_ans2 &= x
	elif com == '|':
		mask_ans1 |= x
		mask_ans2 |= x
	elif com == '^':
		mask_ans1 ^= x
		mask_ans2 ^= x
ans11 = 1023 & ~mask_ans2
ans12 = mask_ans1
ans13 = 1023 & (1023 ^ mask_ans1)
ans1 = 1023 ^ 1023 & ~mask_ans1 & ans11
ans2 = mask_ans2 & ans12
ans3 = 1023 & (mask_ans2 ^ 0) & ans13
lst = []
cnt = 3
if ans1 == 1023:
	cnt -= 1
if ans2 == 0:
	cnt -= 1
if ans3 == 0:
	cnt -= 1
print(cnt)
if ans1 != 1023:
	print('&', ans1)
if ans2 != 0:
	print('|', ans2)
if ans3 != 0:
	print('^', ans3)


import sys, math

def main():
	ops = getops(sys.stdin)
	n1 = 0
	n2 = 1023
	for op in ops:
		n1 = calc(op, n1)
		n2 = calc(op, n2)
	if n2 == 1023 and n1 == 0:
		print(0)
	else:
		and_ = 1023
		or_ = 0
		xor_ = 0
		for i in range(10):
			b1 = n1 % 2
			b2 = n2 % 2
			n1 = n1 // 2
			n2 = n2 // 2
			if b1 == 1 and b2 == 1:
				or_ = or_ | 2 ** i
			elif b1 == 1 and b2 == 0:
				xor_ = xor_ | 2 ** i
			elif b1 == 0 and b2 == 0:
				and_ = and_ - 2 ** i
		print(3)
		print('&', and_)
		print('|', or_)
		print('^', xor_)

def getops(fh):
	n = int(fh.readline())
	ops = []
	for i in range(n):
		(opi, numi) = fh.readline().split()
		numi = int(numi)
		ops.append((opi, numi))
	return ops

def calc(op, res):
	(opi, numi) = op
	if opi == '|':
		res = res | numi
	elif opi == '&':
		res = res & numi
	else:
		res = res ^ numi
	return res
main()