def B():
from string import ascii_uppercase
abc = ["."] + list(ascii_uppercase)
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
for i in range(H):
print(*[abc[A[i][j]] for j in range(W)], sep="")test_all(B)
def B():
from string import ascii_uppercase as ABC
ABC = "." + ABC
H, _ = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
for a in A:
print(*map(lambda x: ABC[x], a),sep="")test_all(B)
def C():
N, M = map(int, input().split())
A = [(x, "A") for x in map(int, input().split())]
B = [(x, "B") for x in map(int, input().split())]
*C, = enumerate(sorted(A + B), 1)
print(*[i for i, (x, AorB) in C if AorB == "A"])
print(*[i for i, (x, AorB) in C if AorB == "B"])test_all(C)
def C():
input()
*A, = [(a, "A") for a in map(int, input().split())]
*B, = [(b, "B") for b in map(int, input().split())]
ansA = []
ansB = []
for i, (_, AorB) in enumerate(sorted(A + B), 1):
if AorB == "A": ansA.append(i)
else: ansB.append(i)
print(*ansA)
print(*ansB)test_all(C)
class BIT:
def __init__(self, a):
if hasattr(a, "__iter__"):
self.size = len(a)
self.data = [0] * self.size
self.bit = [0] * (self.size + 1)
for i, j in enumerate(a):
self.add(i, j)
elif isinstance(a, int):
self.size = a
self.data = [0] * a
self.bit = [0] * (a + 1)
else:
raise TypeError()
def add(self, i, x):
self.data[i] += x
i += 1
while i <= self.size:
self.bit[i] += x
i += i & -i
def sum(self, i):
'''Get sum of data[:i]
'''
total = 0
while i > 0:
total += self.bit[i]
i -= i & -i
return total
def get(self, x):
res = 0
i = 1
while i < (self.size + 1) / 2: i <<= 1
while i > 0:
if res + i < self.size and self.bit[res + i] < x:
x -= self.bit[res + i]
res += i
i >>= 1
res += 1
return res if res >= x else -1
def __getitem__(self, key):
return self.data[key]
def __setitem__(self, key, value):
self.add(key, value - self[key])
self.data[key] = value
def __len__(self):
return self.size
def __repr__(self):
return self.data.__repr__()
def __iter__(self):
return self.data.__iter__()def D():
N, Q = map(int, input().split())
no_called = BIT([0] + [1] * N)
called_no_gone = BIT(N + 1)
for _ in range(Q):
# print(no_called.data)
# print(called_no_gone.data)
ev, *x = input().split()
if ev == "1":
i = no_called.get(1) - 1
no_called[i] = 0
called_no_gone[i] = 1
elif ev == "2":
called_no_gone[int(x[0])] = 0
else:
print(called_no_gone.get(1) - 1)test_all(D)
def D():
N, Q = map(int, input().split())
gone = [False] * (N + 1)
ans = 1
for _ in range(Q):
ev, *x = input().split()
if ev == "1":
pass
elif ev == "2":
gone[int(x[0])] = True
else:
while gone[ans]: ans += 1
print(ans)test_all(D)
def E():
L, N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
B = [list(map(int, input().split())) for i in range(M)]
ans, i, j, p, q = 0, 0, 0, 0, 0
while i < N and j < M:
if A[i][0] == B[j][0]:
ans += min(p + A[i][1], q + B[j][1]) - max(p, q)
if p + A[i][1] < q + B[j][1]:
p += A[i][1]
i += 1
else:
q += B[j][1]
j += 1
print(ans)test_all(E)
def F():
from itertools import product
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
CD = [list(map(int, input().split())) for _ in range(M)]
c = list()
for n, m in product(range(N), range(M)):
c.append((AB[n][0] + CD[m][0]) / (sum(AB[n]) + sum(CD[m])))
print(sorted(c, reverse=True)[K - 1] * 100)test_all(F)
def F():
from bisect import bisect
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
CD = [list(map(int, input().split())) for _ in range(M)]
NG = 0
OK = 1
for i in range(100):
x = (NG + OK) / 2
z = x / (1 - x)
v = sorted([CD[j][0] - CD[j][1] * z for j in range(M)])
num = 0
for j in range(N):
w = AB[j][0] - AB[j][1] * z
num += M - bisect(v, -w)
if num < K: OK = x
else: NG = x
print(OK * 100)test_all(F)
AtCoder Inc.
