template.py

import hashlib, itertools, math, re, string, time

from collections import deque

start = time.time()

def runtime():
	return time.time() - start

dirs = {
	"E": 1, "N": 1j, "W": -1, "S": -1j,
	"e": 1, "n": 1j, "w": -1, "s": -1j,
	">": 1, "^": 1j, "<": -1, "v": -1j,    "V": -1j,
	"R": 1, "U": 1j, "L": -1, "D": -1j,
	"r": 1, "u": 1j, "l": -1, "d": -1j,
	        "T": 1j,          "B": -1j,
	        "t": 1j,          "b": -1j,
	"right": 1, "up": 1j, "left": -1, "down": -1j
}

dirpairs = {k: {1: (1, 0), 1j: (0, -1), -1: (-1, 0), -1j: (0, 1)}[dirs[k]] for k in dirs}

def bitor(x, y): return x | y
def bitand(x, y): return x & y
def xor(x, y): return x ^ y
def lshift(x, y): return x * 2 ** y
def rshift(x, y): return x // 2 ** y
def add(x, y): return x + y
def sub(x, y): return x - y
def mul(x, y): return x * y
def div(x, y): return x / y
def fdiv(x, y): return x // y
def ceil(x): return int(math.ceil(x))
def cdiv(x, y): return ceil(x / y)
def exp(x, y): return x ** y
def root(x, y = 2): return x ** (1 / y)
def eq(x, y): return x == y

def trans(s, m, regex = False):
	o = []
	index = 0
	while s:
		for k in m:
			q = None
			if not regex and s.startswith(k):
				q = k
			elif regex:
				w = re.match(k, s)
				if w:
					q = w.group()
			if q is not None:
				try:
					o.append(m[k](q, index))
				except:
					try:
						o.append(m[k](q))
					except:
						o.append(m[k])
				index += len(q)
				s = s[len(q):]
				break
		else:
			index += 1
	return o

def cumsum(a, s = 0):
	o = [s]
	for i in a:
		o.append(o[-1] + i)
	return o

def lines(f = lambda a: a):
	a = []
	while True:
		try:
			a.append(f(input()))
		except:
			return a

def blocks(f = lambda a: a):
	a = []
	x = ""
	while True:
		try:
			line = input()
			if line.strip():
				x += ("\n" if x else "") + line
			else:
				a.append(f(x))
				x = ""
		except:
			if x:
				a.append(f(x))
			return a

def map(f, a):
	return [f(x) for x in a]

def maps(f, a):
	return [f(*x) for x in a]

def fmap(f, a):
	if type(a) == str and len(a) == 1:
		return f(a)
	try:
		return [fmap(f, x) for x in a]
	except:
		return f(a)

def splitint(s, d):
	return map(int, splittrim(s, d))

def splittrim(s, d):
	return [x.strip() for x in s.split(d)]

def vecop(a, b, op):
	o = []
	try:
		t_ = type(a)
		a = list(a)
		t = t_
		try:
			t_ = type(b)
			b = list(b)
			t = t_
		except:
			b = [b] * len(a)
	except:
		try:
			t_ = type(b)
			b = list(b)
			t = t_
			a = [a] * len(b)
		except:
			return a + b
	for i in range(max(len(a), len(b))):
		if i >= len(a):
			o.append(b[i])
		elif i >= len(b):
			o.append(a[i])
		else:
			o.append(vecop(a[i], b[i], op))
	return t(o)

def vecadd(a, b):
	return vecop(a, b, add)

def surfacearea(a, b, c):
	return 2 * (a * b + b * c + c * a)

def foldl(f, a, b = None):
	return foldr(f, a[::-1], b)

def foldr(f, a, b = None):
	if b is None:
		if len(a) == 0: return None
		b = a[0]
		a = a[1:]
	for i in a:
		b = f(b, i)
	return b

def cumfoldl(f, a, b = None):
	return cumfoldr(f, a[::-1], b)

def cumfoldr(f, a, b = None):
	if b is None:
		if len(a) == 0: return []
		b = a[0]
		a = a[1:]
	r = [b]
	for i in a:
		r.append(f(r[-1], i))
	return r

def product(a, base = 1):
	return foldr(mul, a, base)

def cumprod(a, base = 1):
	return cumfoldr(mul, a, base)

def modunzip(a, m = 2):
	o = [[] for _ in range(m)]
	for i, e in enumerate(a):
		o[i % m].append(e)
	return o

def inf(start = 0):
	while True:
		yield start
		start += 1

def filter(f, a):
	return [x for x in a if f(x)]

def filters(f, a):
	return [x for x in a if f(*x)]

def counts(s, a):
	return sum(s.count(x) for x in a)

def ucounts(s, a):
	return sum(x in s for x in a)

def patternmatch(p, s, strict = False):
	if len(p) != len(s):
		return False
	m = {}
	v = set()
	for a, b in zip(p, s):
		if a in m:
			if b != m[a]:
				return False
		else:
			if strict and b in v:
				return False
			v.add(b)
			m[a] = b
	return True

def patternsearch(p, s, strict = False):
	for k in oslices(s, len(p)):
		if patternmatch(p, k, strict):
			return k
	return None

def cut(s, n):
	i = len(s) % n
	q = len(s) // n
	a = []
	for _ in range(n):
		a.append(s[:q + (i > 0)])
		s = s[q + (i > 0):]
		i -= 1
	return a

def slices(s, l, include_tail = False):
	a = []
	for i in range(0, len(s) // l):
		a.append(s[i * l:i * l + l])
	if len(s) % l and include_tail:
		a.append(s[-(len(s) % l):])
	return a

def oslices(s, l, wrap = False):
	if wrap: s += s[:l - 1]
	a = []
	for i in range(len(s) - l + 1):
		a.append(s[i:i + l])
	return a

def allslices(s, ml = 1):
	return [x for l in range(ml, len(s)) for x in oslices(s, l)]

def getints(s, positive = False):
	return map(int, re.findall(r"\d+" if positive else r"-?\d+", s))

def grid(fill, *dimensions):
	if len(dimensions) == 0:
		return fill
	return [grid(fill, *dimensions[1:]) for _ in range(dimensions[0])]

def gridsum(g):
	if type(g) == str and len(g) == 1:
		return g
	try:
		return sum(map(gridsum, g))
	except:
		return g

def listify(x):
	try:
		return list(x)
	except:
		return [x]

def tighten(x):
	return [e for a in x for e in listify(a)]

def flatten(x):
	if type(x) == str and len(x) == 1:
		return x
	try:
		return tighten(map(flatten, x))
	except:
		return x

def invariant(f, a):
	return f(a) == a

def fixedpoint(f, a):
	b = f(a)
	while b != a:
		a, b = b, f(b)
	return b

def whileunique(f, a, k = lambda x: x):
	v = {k(a)}
	b = f(a)
	q = k(b)
	while q not in v:
		v.add(q)
		b = f(b)
		q = k(b)
	return b

def cumfp(f, a):
	x = [a]
	while True:
		b = f(x[-1])
		if b != x[-1]:
			x.append(b)
		else:
			break
	return x

def cumwu(f, a, k = lambda x: x):
	v = {k(a)}
	r = [a]
	b = f(a)
	q = k(b)
	while q not in v:
		v.add(q)
		r.append(b)
		b = f(b)
		q = k(b)
	return r

def memoize(f):
	cache = {}
	def _inner(*a):
		if a in cache:
			return cache[a]
		v = f(*a)
		cache[a] = v
		return v
	return _inner

def permutations(a, l = None):
	if l is None: l = len(a)
	return map(list, itertools.permutations(a, l))

def combinations(a, l = None):
	if l is None: l = len(a)
	return map(list, itertools.permutations(a, l))

def rle(a):
	encode = []
	for i in a:
		if encode == [] or encode[-1][0] != i:
			encode.append([i, 1])
		else:
			encode[-1][1] += 1
	return encode

def rld(a):
	res = []
	for i, r in a:
		res.extend([i] * r)
	return res

def inclower(s):
	if s == "":
		return "a"
	if s[-1] == "z":
		return inclower(s[:-1]) + "a"
	return s[:-1] + chr(ord(s[-1]) + 1)

def incupper(s):
	if s == "":
		return "A"
	if s[-1] == "Z":
		return incupper(s[:-1]) + "A"
	return s[:-1] + chr(ord(s[-1]) + 1)

def casematch(s, p):
	a = ""
	for x, y in zip(s, p):
		if y.islower():
			a += x.lower()
		elif y.isupper():
			a += x.upper()
		else:
			a += x
	a += s[len(p):]
	return a

def fit(a, l):
	if l <= len(a):
		return a[:l]
	return fit(a * cdiv(l, len(a)), l)

def maxindex(a):
	return a.index(max(a))

def minindex(a):
	return a.index(min(a))

def maxindexes(a):
	return indexes(a, max(a))

def minindexes(a):
	return indexes(a, min(a))

def indexes(a, e):
	r = []
	for i, x in enumerate(a):
		if x == e:
			r.append(i)
	return r

def partitions(x):
	p = []
	for i in range(1, len(x)):
		for sub in partitions(x[i:]):
			p.append([x[:i]] + sub)
	return p + [[x]]

def intpartitions(x, m = 1):
	if m > x: return []
	p = []
	for i in range(m, x):
		for sub in intpartitions(x - i, i):
			p.append([i] + sub)
	return p + [[x]]

def sumsets(x, c):
	if c == 1:
		return [[x]]
	r = []
	for i in range(x + 1):
		for s in sumsets(x - i, c - 1):
			r.append([i] + s)
	return r

def powerset(s):
	r = []
	for i in range(len(s) + 1):
		r += map(list, itertools.combinations(s, i))
	return r

def gi(a, x, d = 0):
	return a[x] if 0 <= x < len(a) else d

def udlr(x, y = None):
	if y is None:
		return [x - 1j, x + 1, x + 1j, x - 1]
	return [[x, y - 1], [x, y + 1], [x - 1, y], [x + 1, y]]

def neighbors(x, y = None):
	if y is None:
		return [x - 1j - 1, x - 1j, x - 1j + 1, x + 1, x + 1j + 1, x + 1j, x + 1j - 1, x - 1]
	return [[x - 1, y - 1], [x, y - 1], [x + 1, y - 1], [x + 1, y], [x + 1, y + 1], [x, y + 1], [x - 1, y + 1], [x - 1, y]]

def suball(s, a, b):
	r = []
	i = s.find(a)
	while i > -1:
		r.append(s[:i] + b + s[i + len(a):])
		i = s.find(a, i + 1)
	return r

class Max:
	def __lt__(self, b):
		return False
	def __le__(self, b):
		return False
	def __gt__(self, b):
		return True
	def __ge__(self, b):
		return True

class Min:
	def __lt__(self, b):
		return True
	def __le__(self, b):
		return True
	def __gt__(self, b):
		return False
	def __ge__(self, b):
		return False

def factors(x):
	s = set()
	for i in range(1, ceil(x ** 0.5) + 1):
		if x % i == 0:
			s.add(i)
			s.add(x // i)
	return sorted(s)

def factorize(x):
	r = []
	f = 2
	while x > 1:
		while x % f == 0:
			r.append(f)
			x //= f
		if f == 2: f = 3
		else: f += 2
	return r

def factorcounts(x):
	c = {}
	for f in factorize(x):
		c[f] = c.get(f, 0) + 1
	return c

def subsetsumext(a, s, d, n, c):
	dp = [d for _ in range(s + 1)]
	for x in a:
		if x > s: continue
		dp[x] = n(x, dp[x])
		for i in range(s, x - 1, -1):
			dp[i] = c(dp[i], dp[i - x], i, x)
	return dp[s]

def subsetsums(a, s):
	return subsetsumext(a, s, 0, lambda _, x: x + 1, lambda x, y, _, __: x + y)

def minlensubsetsum(a, s):
	return subsetsumext(a, s, len(a) + 1, lambda _, x: min(x, 1), lambda x, y, _, __: min(x, y + 1))

def subsetsum(a, s):
	return subsetsumext(a, s, (), lambda _, x: (x,), lambda a, b, _, x: b + (x,))

def factorial(x):
	return int(math.gamma(x + 1))

def choose(n, r):
	return factorial(n) // factorial(r) // factorial(n - r)

def pick(n, r):
	return factorial(n) // factorial(n - r)

def confine(x, mn, mx):
	return min(max(x, mn), mx)

def transform(m):
	return map(list, zip(*m))

@memoize
def MD5(s):
	return hashlib.md5(bytes(s, "utf-8")).hexdigest()

def modes(x, inverse = False):
	k = {}
	for a in x:
		k[a] = k.get(a, 0) + 1
	m = (min if inverse else max)(k.values())
	return [y for y in k if k[y] == m]

def mode(x, inverse = False):
	return modes(x, inverse)[0]

def rotate(a, x):
	x %= len(a)
	return a[-x:] + a[:-x]

def getall(a, i):
	return [a[x] for x in i]

def bfs(start, end, transitions, filter = lambda x: True, key = lambda x: x, ms = Max(), retval = False):
	q = deque()
	q.append((0, start))
	try:
		if end(start):
			return 0
		v = set()
	except:
		end = key(end)
		qq = key(start)
		if qq == end:
			return 0
		elif 0 >= ms:
			return -1
		v = {qq}
	while q:
		s, c = q.popleft()
		for n in transitions(c):
			if not filter(n):
				continue
			k = key(n)
			try:
				if end(n):
					if retval: return (s + 1, n)
					else: return s + 1
			except:
				if k == end:
					if retval: return (s + 1, n)
					else: return s + 1
			if k in v:
				continue
			v.add(k)
			if s + 1 < ms:
				q.append((s + 1, n))
	return -1

def bff(start, transitions, filter = lambda x: True, key = lambda x: x, ms = Max()):
	q = deque()
	q.append((0, start))
	v = {key(start)}
	t = [start]
	if 0 >= ms: return t
	while q:
		s, c = q.popleft()
		for n in transitions(c):
			if not filter(n):
				continue
			k = key(n)
			if k in v:
				continue
			v.add(k)
			t.append(n)
			if s + 1 < ms:
				q.append((s + 1, n))
	return t

def tuplify(x):
	try:
		return tuple(map(tuplify, x))
	except:
		return x

def chain(*fs):
	if len(fs) == 0:
		return lambda x: x
	def _inner(*a, **k):
		x = fs[0](*a, **k)
		for f in fs[1:]:
			x = f(x)
		return x
	return _inner

def clone(x):
	try:
		return type(x)(map(clone, x))
	except:
		return x

def splat(f):
	return lambda x: f(*x)

def unsplat(f):
	return lambda *x: f(x)

def tobase(x, b):
	a = []
	while x:
		a.append(x % b)
		x //= b
	return a[::-1]

def frombase(a, b):
	t = 0
	for x in a:
		t *= b
		try:
			t += x
		except:
			t += int(x, b)
	return t

def hamming(x, b = 2):
	a = tobase(x, b)
	return len(a) - counts(a, [0])

def findMD5(salt, valid, i = 0):
	h = MD5(salt + str(i))
	while True:
		try:
			if valid(h):
				return i
		except:
			if valid(h, i):
				return i
		i += 1
		h = MD5(salt + str(i))

def repeat(f, x):
	if x == 0:
		return lambda x: x
	def _inner(*a, **k):
		y = f(*a, **k)
		for _ in range(x - 1):
			y = f(y)
		return y
	return _inner

def GCD(*a):
	if len(a) == 0:
		raise RuntimeError("GCD of empty sequence")
	if len(a) == 1:
		return a[0]
	g = math.gcd(a[0], a[1])
	for x in a[2:]:
		g = math.gcd(g, x)
	return g

def LCM(*a):
	if len(a) == 0:
		raise RuntimeError("LCM of empty sequence")
	counts = factorcounts(a[0])
	for x in a[1:]:
		c = factorcounts(x)
		for k in c:
			counts[k] = max(counts.get(k, 0), c[k])
	return product(k ** counts[k] for k in counts)

def gountil(start, end, next = lambda x: x + 1, exclude = True):
	while (exclude and start < end) or (not exclude and start <= end):
		yield start
		start = next(start)

def mdindex(a, x):
	q = a
	for i in x:
		q = q[i]
	return q

def mdi(a, x, d = 0):
	q = a
	for i in x:
		if 0 <= i < len(q):
			q = q[i]
		else:
			return d
	return q

def mdslice(a, x):
	if len(x) == 0: return a
	return (type(a))(mdslices(k, x[1:]) for k in a[slice(*x[0])])

def head(a, x):
	r = []
	for i in a:
		r.append(i)
		x -= 1
		if x <= 0:
			return r

def tail(a, x = 1):
	for i in a:
		if x > 0:
			x -= 1
		else:
			yield i

def genaccess(a, i):
	for x in a:
		if i == 0:
			return x
		i -= 1
	raise RuntimeError("Generator did not return enough values")

def genindex(a, x):
	i = 0
	for e in a:
		if e == x:
			return i
		i += 1
	return -1

def partial(f, *x):
	def _inner(*a, **k):
		args = list(x)
		o = 0
		for i in range(len(args)):
			if args[i] is None:
				args[i] = a[0]
				o += 1
		return f(*args, *a[o:], **k)
	return _inner

def splitter(x):
	return lambda s: s.split(x)

def mht(x, y = None):
	if y is None:
		return abs(x.real) + abs(x.imag)
	else:
		return abs(x) + abs(y)

def applymask(mask, original, fallthrough = " "):
	return [y if x in fallthrough else x for x, y in zip(mask, original)]