from typing import List

# Create a node
class BTreeNode:
    def __init__(self, leaf=False, level=0):
        self.leaf = leaf
        self.keys: List[int] = []
        self.child: List["BTreeNode"] = []

# B-Tree
class BTree:
    def __init__(self, t: int):
        # tは次数, nodeのchildがどのサイズになるまで許容するか
        self.root = BTreeNode(True, 0)
        self.t = t

    def insert(self, key):
        root = self.root
        # キーの長さが次数を超えていたら分割
        if len(root.keys) == (2 * self.t) - 1:
            temp = BTreeNode(leaf=False)
            self.root = temp
            temp.child.insert(0, root)
            self.split_child(temp, 0)
            self.insert_non_full(temp, key)
        else:
            self.insert_non_full(root, key)

    def insert_non_full(self, x: "BTreeNode", key):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append(None)
            while i >= 0 and key < x.keys[i]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = key
        else:
            while i >= 0 and key < x.keys[i]:
                i -= 1
            i += 1
            if len(x.child[i].keys) == (2 * self.t) - 1:
                self.split_child(x, i)
                if key > x.keys[i]:
                    i += 1
            self.insert_non_full(x.child[i], key)

    def split_child(self, x, i):
        t = self.t
        y = x.child[i]
        z = BTreeNode(y.leaf)
        x.child.insert(i + 1, z)
        x.keys.insert(i, y.keys[t - 1])
        z.keys = y.keys[t: (2 * t) - 1]
        y.keys = y.keys[0: t - 1]
        if not y.leaf:
            z.child = y.child[t: 2 * t]
            y.child = y.child[0: t - 1]

    def search_key(self, key, x=None, lv=0):
        if x is not None:
            # key > x.keyとなる最小のiを見つける
            # 見つからなかったら次の子供へ移動
            i = 0
            while i < len(x.keys) and key > x.keys[i]:
                i += 1
            # key = x.keyとなるkeyが見つかったらinstanceとレベル(深さ)を返す
            if i < len(x.keys) and key == x.keys[i]:
                return (x, lv)
            elif x.leaf:
                return None
            else:
                return self.search_key(key, x.child[i], lv+1)
        else:
            return self.search_key(key, self.root)

    @staticmethod
    def print_tree(x, lv=0):
        print(f"Level {lv}, size={len(x.keys)}, "
              f"keys={':'.join(map(str, x.keys))}")
        lv += 1
        if len(x.child) > 0:
            for i in x.child:
                BTree.print_tree(i, lv)

import random
# 次数を3に設定
btree = BTree(3)

# 8とランダムに5%をキーとして登録
for key in range(1000):
    if (key != 8) and random.random() < 0.95:
        continue
    btree.insert(key)

# 構造をプリント
BTree.print_tree(btree.root)

# 8のキーを検索
if btree.search_key(8) is not None:
    print("Found")
    print(btree.search_key(8))
else:
    print("Not Found")