from math import * from itertools import combinations,accumulate from collections import defaultdict,deque,Counter from heapq import heapify,heappush,heappop from bisect import bisect,insort def II(): return int(input()) def LI(): return list(map(int,input().split())) def matrix1(n1,v):return [v for _ in range(n1)] def matrix2(n1,n2,v):return [matrix1(n2,v) for _ in range(n1)] def matrix3(n1,n2,n3,v):return [matrix2(n2,n3,v) for _ in range(n1)] def matrix4(n1,n2,n3,n4,v):return [matrix3(n2,n3,n4,v) for _ in range(n1)] #def inside(i, j):return 0<=i