import math
import cmath
import sys
import string
import heapq
import bisect
import copy
from queue import Queue, PriorityQueue, LifoQueue
from collections import Counter, deque
from itertools import permutations, combinations
from functools import cmp_to_key