20240204

# '''

# Q4880

# "append" = put in set (can increase infinitely)

# set [n][m] = (n,m) of the set matrix

# remember that 0 = 1st one

#

# ex) set:

# 500 200 200 100

# 800 370 300 120

# 700 250 300 90

#

# set[0][0] => 500 (1st row 1st column)

# set[2][1] => 250 (3rd row 2nd column)

# '''

# N, K = input().split()

# N = int(N)

# K = int(K)

# time = 0

# money = 0

# set = []

# for i in range(N):

# Wt, Wm, Bt, Bm = input().split()

# Wt = int(Wt)

# Wm = int(Wm)

# Bt = int(Bt)

# Bm = int(Bm)

# set.append([Wt, Wm, Bt, Bm])

# '''not this: (but leaving for future ref anyways)'''

# if (time + Wt <= K) and (time + Bt <= K):

# if Wt/Wm > Bt/Bm:

# time += Wt

# money += Wm

# elif Wt/Wm <= Bt/Bm:

# time += Bt

# money += Bm

# elif (time + Wt > K) and (time + Bt <= K):

# time += Bt

# money += Bm

#

# '''Q1279'''

# a, b = input().split()

# a = int(a)

# b = int(b)

# z = 0

# for i in range(a, b+1):

# if i%2 == 0:

# z -= i

# elif i%2 == 1:

# z += i

# print(z)

#

# '''Q1280'''

# a, b = input().split()

# a = int(a)

# b = int(b)

# z = 0

# for i in range (a,b+1):

# if i % 2 == 0:

# z -= i

# print('-', i, end='', sep='')

# if i % 2 == 1:

# z += i

# print('+',i,end='',sep='')

# print('=', z, sep='')

#

# '''Q1281'''

# a, b = input().split()

# a = int(a)

# b = int(b)

# z = 0

# if a % 2 == 0:

# z -= a

# print('-', a, end='', sep='')

# elif a % 2 == 1:

# z += a

# print(a, end='', sep='')

# for i in range(a+1, b+1):

# if i % 2 == 0:

# z -= i

# print('-', i, end='', sep='')

# if i % 2 == 1:

# z += i

# print('+', i, end='', sep='')

# print('=', z, sep='')

# '''

# 중첩 반복문

# n = int(input())

#

# for i in range(n):

# for j in range(n):

# print('*(%d,%d)\t' %(i, j), end='')

# print()

# '''

# '''Q1352'''

# n = int(input())

# for i in range(n):

# for j in range (n):

# print('*', end='')

# print()

# '''Q1356'''

# n = int(input())

# z = ' '

# print('*'*n)

# for i in range(n-2):

# print('*', z*(n-2), '*', sep='')

# print('*'*n)

# '''Q1365'''

# n = int(input())

#

# for i in range(n): # 0,1,2,3,4

# for j in range(n):

# if i == 0 or j == 0 or i == n-1 or j == n-1 or i == j or j == n-1-i:

# print('*', end='')

# else:

# print(' ', end='')

# print()

# '''Q1366'''

# n = int(input())

# m = n // 2

# for i in range(n):

# for j in range(n):

# if i == 0 or j == 0 or i == n-1 or j == n-1 or i == m or j == m or i == j or j == n-1 - i:

# print('*', end='')

# else:

# print(' ', end='')

# print()

# '''Q1369'''

# n, k = input().split()

# n = int(n)

# k = int(k)

# for i in range(n):

# for j in range(n):

# if i == 0 or j == 0 or i == n-1 or j == n-1 or (i+j+1)%k == 0:

# print('*', end='')

# else:

# print(' ', end='')

# print()

# (1, 1) / (1, 4) / (1, 7)

# (2, 3) / (2, 6)

# (3, 2) / (3, 5) / (3, 9)

# (4, 1) / (4, 4) / (4, 7)

# (5, 3) / (5, 6)

# (6, 2) / (6, 5) / (6, 9)

# (7, 1) / (7, 4) / (7, 7)

# (8, 2) / (8, 6)

# '''Q1353'''

# # n = int(input())

# # for i in range(1, n+1):

# # print('*'*i)

#

# '''Q1354'''

# n = int(input())

# for i in range(1, n+1):

# for j in range(1, n+1):

# if n+1 - i < j:

# print(' ', end='')

# else:

# print('*', end='')

# print()

# '''Q1355'''

# n = int(input())

# for i in range(1, n+1):

# for j in range(1, n+1):

# if ji:

# print(' ', end='')

# else:

# print('*', end='')