fgshun

from collections import deque
from collections.abc import Sequence
from numbers import Real
from typing import TypeVar

T = TypeVar("T", bound=Real)


def sliding_window_minimum(L: Sequence[T], K: int) -> Sequence[T]:
    """スライド最小値

fgshun

from pathlib import Path
from operator import truediv
from functools import reduce

from dagster import (
    Definitions,
    ConfigurableIOManager,
    DailyPartitionsDefinition,
    asset,
    AssetExecutionContext,

fgshun

"""桁 DP の練習"""


def count(N):
    """N 以下の非負整数の数
    
    つまり、ただの N + 1 を動的計画法で回りくどく算出している。
    """
    zero = ord(b'0')

fgshun

import sys
from io import BytesIO


class LCA:
    """LCA 最近共通祖先

    参考
    アルゴリズムロジック - ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）を求めるアルゴリズム
    https://algo-logic.info/lca/

fgshun

"""行列の転置や90度回転など
"""


def transpose(D):
    """転置、 numpy ndarray や pandas.DataFrame だと .T で行うやつ"""
    return list(zip(*D))


def rotate90(D):

fgshun

from heapq import heapify, heappop, heappush, heappushpop, heapreplace
from operator import neg


class MaxHeap:
    def __init__(self, iterator):
        self.seq = list(map(neg, iterator))
        heapify(self.seq)

    def push(self, v):

fgshun

class array2D:
    def __init__(self, H, W):
        self.H = H
        self.W = W
        self._list = [0] * (H * W)

    def __getitem__(self, index):
        if isinstance(index, tuple):
            if not (0 <= index[0] < self.H and 0 <= index[1] < self.W):
                raise IndexError

fgshun

class PascalTriangle:
    def __init__(self, n):
        t = [[1.0]]
        for i in range(2, n + 1):
            row = t[i - 2]
            temp = [1.0]
            for j in range(i - 2):
                # temp.append(t[i - 2][j] + t[i - 2][j + 1])
                # temp.append(sum(t[i - 2][j:j + 2]))
                temp.append(sum(row[j:j + 2]))

fgshun

from __future__ import annotations

import operator
import random
from functools import partialmethod
from typing import (Any, Generic, Iterable, Iterator, List, MutableSequence,
                    Optional, Tuple, TypeVar, Union, overload)

T = TypeVar('T', bound=float)

fgshun

import sys
from itertools import islice
from operator import itemgetter


class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.par = list(range(n))
        self.rank = [0] * n