inspirit941

from itertools import combinations
import math
def solution(nums):
    candidates = combinations(nums, 3)
    answer = 0
    for item in candidates:
        sums = sum(item)
        is_prime = True
        for i in range(2, int(math.sqrt(sums)) + 1):
            if sums % i == 0:

inspirit941

def solution(n):
    cnt = 0
    while n > 0:
        q, r = divmod(n, 2)
        n = q
        if r != 0:
            cnt += 1
    return cnt

inspirit941

# deque rotate 양수 = 시계방향, 음수 = 반시계방향
from collections import deque
import sys
from itertools import chain

def bfs(maps, y, x):
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    queue = deque()
    value = maps[y][x]
    queue.append((y, x))

inspirit941

def solution(N):
    line = [0] * N
    line[0], line[1] = 1,1
    idx = 2
    while idx < len(line):
        line[idx] = line[idx-1] + line[idx-2]
        idx += 1
    return line[-1] * 4 + line[-2] * 2

inspirit941

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
import sys
def find_parent(x, parent):
	if x not in parent or x == parent[x]:
		return x
	p = find_parent(parent[x], parent)
	parent[x] = p
	return p

inspirit941

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
# 보유해야 할 힘의 양
answer = 0

# 뒤에서부터 계산하면
for idx in range(len(arr)-1, 0, -1):

inspirit941

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
import math, sys
from itertools import permutations
def check_prime(n):
	for i in range(2, int(math.sqrt(n) + 1)):
		if n % i == 0:
			return False
	return True
n = int(sys.stdin.readline())

inspirit941

import sys
import math
n, q = map(int, sys.stdin.readline().split())
# 잡초
maps = list(map(int, sys.stdin.readline().split()))
# 트리를 위한 배열 크기
# N이 2 * 10**5. log_2(N) = 1 + 5*log_2(2*5)
# print(5 * math.log(10, 2)) = 16.610 정도 된다. 즉 배열 크기는 17은 넘어야 한다
# print(2**17) = 131072, print(2**18) = 262144
# 트리니까 2**18 값에 * 2를 하면 모든 연산값을 담을 수 있는 배열을 만들 수 있다.

inspirit941

import sys
import math
n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

answer = math.inf
# 가장 작은 숫자가 맨 앞일 때... 맨 뒤일 때까지.
start_idx = arr.index(min(arr))
for i in range(k):
	cnt = 1

inspirit941

from collections import defaultdict
def solution(K, travel):
    # dfs(0, travel, K, 0, 0)
    # table[n][key] = n번째 도시를 key의 시간으로 방문할 때 모금액의 최댓값
    answer = 0
    table = [defaultdict(int) for _ in range(100)]
    table[0][travel[0][0]] = travel[0][1] if travel[0][0] <= K else 0
    table[0][travel[0][2]] = travel[0][3] if travel[0][2] <= K else 0
    for n in range(1, len(travel)):
        for key in table[n-1]: