# fields_and_stones_longest.py
import random
import time
import sys
 
# Налаштування рекурсії
sys.setrecursionlimit(10000)
 
# ------------------------
# Генерація поля
# 0 = поле ('.'), 1 = камінь ('#')
# ------------------------
def generate_field(N, M, p):
    grid = [[1 if random.random() < p else 0 for _ in range(M)] for _ in range(N)]
    grid[N-1][0] = 0   # старт (лівий нижній)
    grid[0][M-1] = 0   # фініш (правий верхній)
    return grid
 
# ------------------------
# Коротка перевірка існування шляху (BFS) перед тривалим DFS
# щоб не запускати довгий пошук коли шлях зовсім відсутній
# ------------------------
from collections import deque
def exists_path_bfs(grid):
    N, M = len(grid), len(grid[0])
    start = (N-1,0)
    goal = (0, M-1)
    if grid[start[0]][start[1]] != 0 or grid[goal[0]][goal[1]] != 0:
        return False
    q = deque([start])
    vis = [[False]*M for _ in range(N)]
    vis[start[0]][start[1]] = True
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    while q:
        r,c = q.popleft()
        if (r,c) == goal:
            return True
        for dr,dc in dirs:
            nr, nc = r+dr, c+dc
            if 0 <= nr < N and 0 <= nc < M and not vis[nr][nc] and grid[nr][nc] == 0:
                vis[nr][nc] = True
                q.append((nr,nc))
    return False
 
# ------------------------
# Пошук найдовшого простого шляху (DFS з відкатом + таймаут)
# Параметри:
#   time_limit - сек., скільки максимум шукати
#   randomize - чи випадково перемішувати порядок сусідів для різноманіття
# Повертає: найкращий шлях як список клітин від старту до фінішу (включно) або None
# ------------------------
def longest_path_dfs(grid, time_limit=1.5, randomize=True):
    N, M = len(grid), len(grid[0])
    start = (N-1, 0)
    goal = (0, M-1)
    dirs = [(1,0), (0,1), (-1,0), (0,-1)]  # порядок можна міняти
    best_path = None
    best_len = -1
    start_time = time.time()
    max_nodes = 10**6
    nodes = 0
 
    # Пріоритет: спробуємо шукати більш глибоко — порядок сусідів можна перемішати
    import random as _rnd
 
    visited = [[False]*M for _ in range(N)]
    path = []
 
    def dfs(r,c):
        nonlocal best_len, best_path, nodes
        # таймаут/лиміт на відвідані вузли
        if time.time() - start_time > time_limit:
            return
        nodes += 1
        if nodes > max_nodes:
            return
 
        # якщо дійшли до goal — оновити кращий шлях
        if (r,c) == goal:
            if len(path) > best_len:
                best_len = len(path)
                best_path = path.copy()
            # не повертаємось далі з goal (нам потрібно goal бути останнім)
            return
 
        # Порядок сусідів: спочатку ті, що ведуть ближче до goal (гіпо), потім інші
        neighs = []
        for dr,dc in dirs:
            nr, nc = r+dr, c+dc
            if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc] and grid[nr][nc] == 0:
                # не заходити в goal, якщо goal вже в path (не буде)
                # обчислимо евклідну відстань або манхеттен
                dist = abs(nr - goal[0]) + abs(nc - goal[1])
                neighs.append((dist, nr, nc))
        # сортуємо за зменшенням відстані -> спочатку ті, що далі від цілі, щоб робити довші «змійки»
        neighs.sort(reverse=True, key=lambda x: x[0])
        if randomize:
            # невелика випадкова перестановка серед тих з однаковою дистанцією
            i = 0
            while i < len(neighs):
                j = i
                while j < len(neighs) and neighs[j][0] == neighs[i][0]:
                    j += 1
                # shuffle block [i, j)
                block = neighs[i:j]
                _rnd.shuffle(block)
                neighs[i:j] = block
                i = j
 
        for _, nr, nc in neighs:
            # якщо досягли ліміту часу, виходимо
            if time.time() - start_time > time_limit:
                return
            # відвідуємо
            visited[nr][nc] = True
            path.append((nr,nc))
            dfs(nr,nc)
            # відкат
            path.pop()
            visited[nr][nc] = False
            # optional pruning: якщо знайшли шлях максимальної можливої довжини (всі поля), можна зупинитися
            # але ми не рахуємо тут максимально можливу глобальну довжину, тому пропускаємо
 
    # початковий захід: старт має бути першою позицією у path
    if grid[start[0]][start[1]] != 0 or grid[goal[0]][goal[1]] != 0:
        return None
 
    visited[start[0]][start[1]] = True
    path.append(start)
    dfs(start[0], start[1])
    # якщо нічого не знайдено (можливо шлях існував тільки прямий) — best_path може бути None
    visited[start[0]][start[1]] = False
    path.pop()
 
    return best_path
 
# ------------------------
# Вивід карти: пронумерований шлях (0 = старт), '.' для незораного, '#' для каменю
# Клітинка має ширину під найбільший індекс
# ------------------------
def print_board_numbered(grid, path):
    N, M = len(grid), len(grid[0])
    step = {}
    if path:
        for i, cell in enumerate(path):
            step[cell] = i
 
    max_step = max(step.values()) if step else 0
    width = max(3, len(str(max_step)) + 2)
 
    def cell_str(s):
        return str(s).center(width)
 
    print()
    for r in range(N):
        row_cells = []
        for c in range(M):
            if (r,c) in step:
                row_cells.append(cell_str(step[(r,c)]))
            elif grid[r][c] == 1:
                row_cells.append(cell_str("#"))
            else:
                row_cells.append(cell_str("."))
        print("".join(row_cells))
    print()
 
# ------------------------
# MAIN (українською)
# ------------------------
def main():
    print("=== Поля і каміння — пошук довгого простого шляху (забезпечує, що фініт останній) ===")
    try:
        N = int(input("Введіть кількість рядків N (1..100): ").strip())
        M = int(input("Введіть кількість стовпців M (1..100): ").strip())
    except Exception:
        print("Некоректні N або M.")
        return
    if not (1 <= N <= 100 and 1 <= M <= 100):
        print("N і M повинні бути від 1 до 100.")
        return
 
    try:
        p = float(input("Ймовірність каменю в клітинці (0..1), наприклад 0.25: ").strip())
        if not (0.0 <= p <= 1.0):
            raise ValueError()
    except Exception:
        print("Некоректне p — використовую 0.25")
        p = 0.25
 
    try:
        tlim = float(input("Часовий ліміт пошуку в секундах (наприклад 1.5): ").strip())
        if tlim <= 0:
            tlim = 1.5
    except Exception:
        tlim = 1.5
 
    regen = input("Якщо потрібно — регенерувати поле поки існує шлях? (т/н) [т]: ").strip().lower()
    regen_flag = (regen == "" or regen == "т" or regen == "y" or regen == "yes")
 
    attempts = 0
    while True:
        attempts += 1
        grid = generate_field(N, M, p)
        if exists_path_bfs(grid):
            break
        if not regen_flag:
            break
        if attempts > 2000:
            print("Не вдалось згенерувати поле з шляхом за багато спроб. Спробуйте змінити p.")
            return
 
    print("\nЗгенероване поле (вирівняне):")
    print_board_numbered(grid, None)
 
    if not exists_path_bfs(grid):
        print("Шляху немає — завершую.")
        return
 
    print(f"Починаємо пошук найдовшого простого шляху (таймаут = {tlim} сек)...")
    best = longest_path_dfs(grid, time_limit=tlim, randomize=True)
 
    if not best:
        print("Не знайдено жодного шляху (неочікувано).")
        return
 
    # best — шлях з старту до фінішу, простий, goal останній
    print(f"Знайдений шлях довжиною {len(best)} (0 = старт).")
    print("\nКарта з пронумерованим шляхом:")
    print_board_numbered(grid, best)
 
    # Додатково: виведемо координати шляху у 1-based
    print("\nКроки шляху (1-based координати):")
    print([(r+1, c+1) for (r,c) in best])
 
if __name__ == "__main__":
    main()
 

IyBmaWVsZHNfYW5kX3N0b25lc19sb25nZXN0LnB5CmltcG9ydCByYW5kb20KaW1wb3J0IHRpbWUKaW1wb3J0IHN5cwoKIyDQndCw0LvQsNGI0YLRg9Cy0LDQvdC90Y8g0YDQtdC60YPRgNGB0ZbRlwpzeXMuc2V0cmVjdXJzaW9ubGltaXQoMTAwMDApCgojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQojINCT0LXQvdC10YDQsNGG0ZbRjyDQv9C+0LvRjwojIDAgPSDQv9C+0LvQtSAoJy4nKSwgMSA9INC60LDQvNGW0L3RjCAoJyMnKQojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQpkZWYgZ2VuZXJhdGVfZmllbGQoTiwgTSwgcCk6CiAgICBncmlkID0gW1sxIGlmIHJhbmRvbS5yYW5kb20oKSA8IHAgZWxzZSAwIGZvciBfIGluIHJhbmdlKE0pXSBmb3IgXyBpbiByYW5nZShOKV0KICAgIGdyaWRbTi0xXVswXSA9IDAgICAjINGB0YLQsNGA0YIgKNC70ZbQstC40Lkg0L3QuNC20L3RltC5KQogICAgZ3JpZFswXVtNLTFdID0gMCAgICMg0YTRltC90ZbRiCAo0L/RgNCw0LLQuNC5INCy0LXRgNGF0L3RltC5KQogICAgcmV0dXJuIGdyaWQKCiMgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiMg0JrQvtGA0L7RgtC60LAg0L/QtdGA0LXQstGW0YDQutCwINGW0YHQvdGD0LLQsNC90L3RjyDRiNC70Y/RhdGDIChCRlMpINC/0LXRgNC10LQg0YLRgNC40LLQsNC70LjQvCBERlMKIyDRidC+0LEg0L3QtSDQt9Cw0L/Rg9GB0LrQsNGC0Lgg0LTQvtCy0LPQuNC5INC/0L7RiNGD0Log0LrQvtC70Lgg0YjQu9GP0YUg0LfQvtCy0YHRltC8INCy0ZbQtNGB0YPRgtC90ZbQuQojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQpmcm9tIGNvbGxlY3Rpb25zIGltcG9ydCBkZXF1ZQpkZWYgZXhpc3RzX3BhdGhfYmZzKGdyaWQpOgogICAgTiwgTSA9IGxlbihncmlkKSwgbGVuKGdyaWRbMF0pCiAgICBzdGFydCA9IChOLTEsMCkKICAgIGdvYWwgPSAoMCwgTS0xKQogICAgaWYgZ3JpZFtzdGFydFswXV1bc3RhcnRbMV1dICE9IDAgb3IgZ3JpZFtnb2FsWzBdXVtnb2FsWzFdXSAhPSAwOgogICAgICAgIHJldHVybiBGYWxzZQogICAgcSA9IGRlcXVlKFtzdGFydF0pCiAgICB2aXMgPSBbW0ZhbHNlXSpNIGZvciBfIGluIHJhbmdlKE4pXQogICAgdmlzW3N0YXJ0WzBdXVtzdGFydFsxXV0gPSBUcnVlCiAgICBkaXJzID0gWygxLDApLCgtMSwwKSwoMCwxKSwoMCwtMSldCiAgICB3aGlsZSBxOgogICAgICAgIHIsYyA9IHEucG9wbGVmdCgpCiAgICAgICAgaWYgKHIsYykgPT0gZ29hbDoKICAgICAgICAgICAgcmV0dXJuIFRydWUKICAgICAgICBmb3IgZHIsZGMgaW4gZGlyczoKICAgICAgICAgICAgbnIsIG5jID0gcitkciwgYytkYwogICAgICAgICAgICBpZiAwIDw9IG5yIDwgTiBhbmQgMCA8PSBuYyA8IE0gYW5kIG5vdCB2aXNbbnJdW25jXSBhbmQgZ3JpZFtucl1bbmNdID09IDA6CiAgICAgICAgICAgICAgICB2aXNbbnJdW25jXSA9IFRydWUKICAgICAgICAgICAgICAgIHEuYXBwZW5kKChucixuYykpCiAgICByZXR1cm4gRmFsc2UKCiMgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCiMg0J/QvtGI0YPQuiDQvdCw0LnQtNC+0LLRiNC+0LPQviDQv9GA0L7RgdGC0L7Qs9C+INGI0LvRj9GF0YMgKERGUyDQtyDQstGW0LTQutCw0YLQvtC8ICsg0YLQsNC50LzQsNGD0YIpCiMg0J/QsNGA0LDQvNC10YLRgNC4OgojICAgdGltZV9saW1pdCAtINGB0LXQui4sINGB0LrRltC70YzQutC4INC80LDQutGB0LjQvNGD0Lwg0YjRg9C60LDRgtC4CiMgICByYW5kb21pemUgLSDRh9C4INCy0LjQv9Cw0LTQutC+0LLQviDQv9C10YDQtdC80ZbRiNGD0LLQsNGC0Lgg0L/QvtGA0Y/QtNC+0Log0YHRg9GB0ZbQtNGW0LIg0LTQu9GPINGA0ZbQt9C90L7QvNCw0L3RltGC0YLRjwojINCf0L7QstC10YDRgtCw0ZQ6INC90LDQudC60YDQsNGJ0LjQuSDRiNC70Y/RhSDRj9C6INGB0L/QuNGB0L7QuiDQutC70ZbRgtC40L0g0LLRltC0INGB0YLQsNGA0YLRgyDQtNC+INGE0ZbQvdGW0YjRgyAo0LLQutC70Y7Rh9C90L4pINCw0LHQviBOb25lCiMgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCmRlZiBsb25nZXN0X3BhdGhfZGZzKGdyaWQsIHRpbWVfbGltaXQ9MS41LCByYW5kb21pemU9VHJ1ZSk6CiAgICBOLCBNID0gbGVuKGdyaWQpLCBsZW4oZ3JpZFswXSkKICAgIHN0YXJ0ID0gKE4tMSwgMCkKICAgIGdvYWwgPSAoMCwgTS0xKQogICAgZGlycyA9IFsoMSwwKSwgKDAsMSksICgtMSwwKSwgKDAsLTEpXSAgIyDQv9C+0YDRj9C00L7QuiDQvNC+0LbQvdCwINC80ZbQvdGP0YLQuAogICAgYmVzdF9wYXRoID0gTm9uZQogICAgYmVzdF9sZW4gPSAtMQogICAgc3RhcnRfdGltZSA9IHRpbWUudGltZSgpCiAgICBtYXhfbm9kZXMgPSAxMCoqNgogICAgbm9kZXMgPSAwCgogICAgIyDQn9GA0ZbQvtGA0LjRgtC10YI6INGB0L/RgNC+0LHRg9GU0LzQviDRiNGD0LrQsNGC0Lgg0LHRltC70YzRiCDQs9C70LjQsdC+0LrQviDigJQg0L/QvtGA0Y/QtNC+0Log0YHRg9GB0ZbQtNGW0LIg0LzQvtC20L3QsCDQv9C10YDQtdC80ZbRiNCw0YLQuAogICAgaW1wb3J0IHJhbmRvbSBhcyBfcm5kCgogICAgdmlzaXRlZCA9IFtbRmFsc2VdKk0gZm9yIF8gaW4gcmFuZ2UoTildCiAgICBwYXRoID0gW10KCiAgICBkZWYgZGZzKHIsYyk6CiAgICAgICAgbm9ubG9jYWwgYmVzdF9sZW4sIGJlc3RfcGF0aCwgbm9kZXMKICAgICAgICAjINGC0LDQudC80LDRg9GCL9C70LjQvNGW0YIg0L3QsCDQstGW0LTQstGW0LTQsNC90ZYg0LLRg9C30LvQuAogICAgICAgIGlmIHRpbWUudGltZSgpIC0gc3RhcnRfdGltZSA+IHRpbWVfbGltaXQ6CiAgICAgICAgICAgIHJldHVybgogICAgICAgIG5vZGVzICs9IDEKICAgICAgICBpZiBub2RlcyA+IG1heF9ub2RlczoKICAgICAgICAgICAgcmV0dXJuCgogICAgICAgICMg0Y/QutGJ0L4g0LTRltC50YjQu9C4INC00L4gZ29hbCDigJQg0L7QvdC+0LLQuNGC0Lgg0LrRgNCw0YnQuNC5INGI0LvRj9GFCiAgICAgICAgaWYgKHIsYykgPT0gZ29hbDoKICAgICAgICAgICAgaWYgbGVuKHBhdGgpID4gYmVzdF9sZW46CiAgICAgICAgICAgICAgICBiZXN0X2xlbiA9IGxlbihwYXRoKQogICAgICAgICAgICAgICAgYmVzdF9wYXRoID0gcGF0aC5jb3B5KCkKICAgICAgICAgICAgIyDQvdC1INC/0L7QstC10YDRgtCw0ZTQvNC+0YHRjCDQtNCw0LvRliDQtyBnb2FsICjQvdCw0Lwg0L/QvtGC0YDRltCx0L3QviBnb2FsINCx0YPRgtC4INC+0YHRgtCw0L3QvdGW0LwpCiAgICAgICAgICAgIHJldHVybgoKICAgICAgICAjINCf0L7RgNGP0LTQvtC6INGB0YPRgdGW0LTRltCyOiDRgdC/0L7Rh9Cw0YLQutGDINGC0ZYsINGJ0L4g0LLQtdC00YPRgtGMINCx0LvQuNC20YfQtSDQtNC+IGdvYWwgKNCz0ZbQv9C+KSwg0L/QvtGC0ZbQvCDRltC90YjRlgogICAgICAgIG5laWdocyA9IFtdCiAgICAgICAgZm9yIGRyLGRjIGluIGRpcnM6CiAgICAgICAgICAgIG5yLCBuYyA9IHIrZHIsIGMrZGMKICAgICAgICAgICAgaWYgMCA8PSBuciA8IE4gYW5kIDAgPD0gbmMgPCBNIGFuZCBub3QgdmlzaXRlZFtucl1bbmNdIGFuZCBncmlkW25yXVtuY10gPT0gMDoKICAgICAgICAgICAgICAgICMg0L3QtSDQt9Cw0YXQvtC00LjRgtC4INCyIGdvYWwsINGP0LrRidC+IGdvYWwg0LLQttC1INCyIHBhdGggKNC90LUg0LHRg9C00LUpCiAgICAgICAgICAgICAgICAjINC+0LHRh9C40YHQu9C40LzQviDQtdCy0LrQu9GW0LTQvdGDINCy0ZbQtNGB0YLQsNC90Ywg0LDQsdC+INC80LDQvdGF0LXRgtGC0LXQvQogICAgICAgICAgICAgICAgZGlzdCA9IGFicyhuciAtIGdvYWxbMF0pICsgYWJzKG5jIC0gZ29hbFsxXSkKICAgICAgICAgICAgICAgIG5laWdocy5hcHBlbmQoKGRpc3QsIG5yLCBuYykpCiAgICAgICAgIyDRgdC+0YDRgtGD0ZTQvNC+INC30LAg0LfQvNC10L3RiNC10L3QvdGP0Lwg0LLRltC00YHRgtCw0L3RliAtPiDRgdC/0L7Rh9Cw0YLQutGDINGC0ZYsINGJ0L4g0LTQsNC70ZYg0LLRltC0INGG0ZbQu9GWLCDRidC+0LEg0YDQvtCx0LjRgtC4INC00L7QstGI0ZYgwqvQt9C80ZbQudC60LjCuwogICAgICAgIG5laWdocy5zb3J0KHJldmVyc2U9VHJ1ZSwga2V5PWxhbWJkYSB4OiB4WzBdKQogICAgICAgIGlmIHJhbmRvbWl6ZToKICAgICAgICAgICAgIyDQvdC10LLQtdC70LjQutCwINCy0LjQv9Cw0LTQutC+0LLQsCDQv9C10YDQtdGB0YLQsNC90L7QstC60LAg0YHQtdGA0LXQtCDRgtC40YUg0Lcg0L7QtNC90LDQutC+0LLQvtGOINC00LjRgdGC0LDQvdGG0ZbRlNGOCiAgICAgICAgICAgIGkgPSAwCiAgICAgICAgICAgIHdoaWxlIGkgPCBsZW4obmVpZ2hzKToKICAgICAgICAgICAgICAgIGogPSBpCiAgICAgICAgICAgICAgICB3aGlsZSBqIDwgbGVuKG5laWdocykgYW5kIG5laWdoc1tqXVswXSA9PSBuZWlnaHNbaV1bMF06CiAgICAgICAgICAgICAgICAgICAgaiArPSAxCiAgICAgICAgICAgICAgICAjIHNodWZmbGUgYmxvY2sgW2ksIGopCiAgICAgICAgICAgICAgICBibG9jayA9IG5laWdoc1tpOmpdCiAgICAgICAgICAgICAgICBfcm5kLnNodWZmbGUoYmxvY2spCiAgICAgICAgICAgICAgICBuZWlnaHNbaTpqXSA9IGJsb2NrCiAgICAgICAgICAgICAgICBpID0gagoKICAgICAgICBmb3IgXywgbnIsIG5jIGluIG5laWdoczoKICAgICAgICAgICAgIyDRj9C60YnQviDQtNC+0YHRj9Cz0LvQuCDQu9GW0LzRltGC0YMg0YfQsNGB0YMsINCy0LjRhdC+0LTQuNC80L4KICAgICAgICAgICAgaWYgdGltZS50aW1lKCkgLSBzdGFydF90aW1lID4gdGltZV9saW1pdDoKICAgICAgICAgICAgICAgIHJldHVybgogICAgICAgICAgICAjINCy0ZbQtNCy0ZbQtNGD0ZTQvNC+CiAgICAgICAgICAgIHZpc2l0ZWRbbnJdW25jXSA9IFRydWUKICAgICAgICAgICAgcGF0aC5hcHBlbmQoKG5yLG5jKSkKICAgICAgICAgICAgZGZzKG5yLG5jKQogICAgICAgICAgICAjINCy0ZbQtNC60LDRggogICAgICAgICAgICBwYXRoLnBvcCgpCiAgICAgICAgICAgIHZpc2l0ZWRbbnJdW25jXSA9IEZhbHNlCiAgICAgICAgICAgICMgb3B0aW9uYWwgcHJ1bmluZzog0Y/QutGJ0L4g0LfQvdCw0LnRiNC70Lgg0YjQu9GP0YUg0LzQsNC60YHQuNC80LDQu9GM0L3QvtGXINC80L7QttC70LjQstC+0Zcg0LTQvtCy0LbQuNC90LggKNCy0YHRliDQv9C+0LvRjyksINC80L7QttC90LAg0LfRg9C/0LjQvdC40YLQuNGB0Y8KICAgICAgICAgICAgIyDQsNC70LUg0LzQuCDQvdC1INGA0LDRhdGD0ZTQvNC+INGC0YPRgiDQvNCw0LrRgdC40LzQsNC70YzQvdC+INC80L7QttC70LjQstGDINCz0LvQvtCx0LDQu9GM0L3RgyDQtNC+0LLQttC40L3Rgywg0YLQvtC80YMg0L/RgNC+0L/Rg9GB0LrQsNGU0LzQvgoKICAgICMg0L/QvtGH0LDRgtC60L7QstC40Lkg0LfQsNGF0ZbQtDog0YHRgtCw0YDRgiDQvNCw0ZQg0LHRg9GC0Lgg0L/QtdGA0YjQvtGOINC/0L7Qt9C40YbRltGU0Y4g0YMgcGF0aAogICAgaWYgZ3JpZFtzdGFydFswXV1bc3RhcnRbMV1dICE9IDAgb3IgZ3JpZFtnb2FsWzBdXVtnb2FsWzFdXSAhPSAwOgogICAgICAgIHJldHVybiBOb25lCgogICAgdmlzaXRlZFtzdGFydFswXV1bc3RhcnRbMV1dID0gVHJ1ZQogICAgcGF0aC5hcHBlbmQoc3RhcnQpCiAgICBkZnMoc3RhcnRbMF0sIHN0YXJ0WzFdKQogICAgIyDRj9C60YnQviDQvdGW0YfQvtCz0L4g0L3QtSDQt9C90LDQudC00LXQvdC+ICjQvNC+0LbQu9C40LLQviDRiNC70Y/RhSDRltGB0L3Rg9Cy0LDQsiDRgtGW0LvRjNC60Lgg0L/RgNGP0LzQuNC5KSDigJQgYmVzdF9wYXRoINC80L7QttC1INCx0YPRgtC4IE5vbmUKICAgIHZpc2l0ZWRbc3RhcnRbMF1dW3N0YXJ0WzFdXSA9IEZhbHNlCiAgICBwYXRoLnBvcCgpCgogICAgcmV0dXJuIGJlc3RfcGF0aAoKIyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KIyDQktC40LLRltC0INC60LDRgNGC0Lg6INC/0YDQvtC90YPQvNC10YDQvtCy0LDQvdC40Lkg0YjQu9GP0YUgKDAgPSDRgdGC0LDRgNGCKSwgJy4nINC00LvRjyDQvdC10LfQvtGA0LDQvdC+0LPQviwgJyMnINC00LvRjyDQutCw0LzQtdC90Y4KIyDQmtC70ZbRgtC40L3QutCwINC80LDRlCDRiNC40YDQuNC90YMg0L/RltC0INC90LDQudCx0ZbQu9GM0YjQuNC5INGW0L3QtNC10LrRgQojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQpkZWYgcHJpbnRfYm9hcmRfbnVtYmVyZWQoZ3JpZCwgcGF0aCk6CiAgICBOLCBNID0gbGVuKGdyaWQpLCBsZW4oZ3JpZFswXSkKICAgIHN0ZXAgPSB7fQogICAgaWYgcGF0aDoKICAgICAgICBmb3IgaSwgY2VsbCBpbiBlbnVtZXJhdGUocGF0aCk6CiAgICAgICAgICAgIHN0ZXBbY2VsbF0gPSBpCgogICAgbWF4X3N0ZXAgPSBtYXgoc3RlcC52YWx1ZXMoKSkgaWYgc3RlcCBlbHNlIDAKICAgIHdpZHRoID0gbWF4KDMsIGxlbihzdHIobWF4X3N0ZXApKSArIDIpCgogICAgZGVmIGNlbGxfc3RyKHMpOgogICAgICAgIHJldHVybiBzdHIocykuY2VudGVyKHdpZHRoKQoKICAgIHByaW50KCkKICAgIGZvciByIGluIHJhbmdlKE4pOgogICAgICAgIHJvd19jZWxscyA9IFtdCiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoTSk6CiAgICAgICAgICAgIGlmIChyLGMpIGluIHN0ZXA6CiAgICAgICAgICAgICAgICByb3dfY2VsbHMuYXBwZW5kKGNlbGxfc3RyKHN0ZXBbKHIsYyldKSkKICAgICAgICAgICAgZWxpZiBncmlkW3JdW2NdID09IDE6CiAgICAgICAgICAgICAgICByb3dfY2VsbHMuYXBwZW5kKGNlbGxfc3RyKCIjIikpCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICByb3dfY2VsbHMuYXBwZW5kKGNlbGxfc3RyKCIuIikpCiAgICAgICAgcHJpbnQoIiIuam9pbihyb3dfY2VsbHMpKQogICAgcHJpbnQoKQoKIyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KIyBNQUlOICjRg9C60YDQsNGX0L3RgdGM0LrQvtGOKQojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQpkZWYgbWFpbigpOgogICAgcHJpbnQoIj09PSDQn9C+0LvRjyDRliDQutCw0LzRltC90L3RjyDigJQg0L/QvtGI0YPQuiDQtNC+0LLQs9C+0LPQviDQv9GA0L7RgdGC0L7Qs9C+INGI0LvRj9GF0YMgKNC30LDQsdC10LfQv9C10YfRg9GULCDRidC+INGE0ZbQvdGW0YIg0L7RgdGC0LDQvdC90ZbQuSkgPT09IikKICAgIHRyeToKICAgICAgICBOID0gaW50KGlucHV0KCLQktCy0LXQtNGW0YLRjCDQutGW0LvRjNC60ZbRgdGC0Ywg0YDRj9C00LrRltCyIE4gKDEuLjEwMCk6ICIpLnN0cmlwKCkpCiAgICAgICAgTSA9IGludChpbnB1dCgi0JLQstC10LTRltGC0Ywg0LrRltC70YzQutGW0YHRgtGMINGB0YLQvtCy0L/RhtGW0LIgTSAoMS4uMTAwKTogIikuc3RyaXAoKSkKICAgIGV4Y2VwdCBFeGNlcHRpb246CiAgICAgICAgcHJpbnQoItCd0LXQutC+0YDQtdC60YLQvdGWIE4g0LDQsdC+IE0uIikKICAgICAgICByZXR1cm4KICAgIGlmIG5vdCAoMSA8PSBOIDw9IDEwMCBhbmQgMSA8PSBNIDw9IDEwMCk6CiAgICAgICAgcHJpbnQoIk4g0ZYgTSDQv9C+0LLQuNC90L3RliDQsdGD0YLQuCDQstGW0LQgMSDQtNC+IDEwMC4iKQogICAgICAgIHJldHVybgoKICAgIHRyeToKICAgICAgICBwID0gZmxvYXQoaW5wdXQoItCZ0LzQvtCy0ZbRgNC90ZbRgdGC0Ywg0LrQsNC80LXQvdGOINCyINC60LvRltGC0LjQvdGG0ZYgKDAuLjEpLCDQvdCw0L/RgNC40LrQu9Cw0LQgMC4yNTogIikuc3RyaXAoKSkKICAgICAgICBpZiBub3QgKDAuMCA8PSBwIDw9IDEuMCk6CiAgICAgICAgICAgIHJhaXNlIFZhbHVlRXJyb3IoKQogICAgZXhjZXB0IEV4Y2VwdGlvbjoKICAgICAgICBwcmludCgi0J3QtdC60L7RgNC10LrRgtC90LUgcCDigJQg0LLQuNC60L7RgNC40YHRgtC+0LLRg9GOIDAuMjUiKQogICAgICAgIHAgPSAwLjI1CgogICAgdHJ5OgogICAgICAgIHRsaW0gPSBmbG9hdChpbnB1dCgi0KfQsNGB0L7QstC40Lkg0LvRltC80ZbRgiDQv9C+0YjRg9C60YMg0LIg0YHQtdC60YPQvdC00LDRhSAo0L3QsNC/0YDQuNC60LvQsNC0IDEuNSk6ICIpLnN0cmlwKCkpCiAgICAgICAgaWYgdGxpbSA8PSAwOgogICAgICAgICAgICB0bGltID0gMS41CiAgICBleGNlcHQgRXhjZXB0aW9uOgogICAgICAgIHRsaW0gPSAxLjUKCiAgICByZWdlbiA9IGlucHV0KCLQr9C60YnQviDQv9C+0YLRgNGW0LHQvdC+IOKAlCDRgNC10LPQtdC90LXRgNGD0LLQsNGC0Lgg0L/QvtC70LUg0L/QvtC60Lgg0ZbRgdC90YPRlCDRiNC70Y/RhT8gKNGCL9C9KSBb0YJdOiAiKS5zdHJpcCgpLmxvd2VyKCkKICAgIHJlZ2VuX2ZsYWcgPSAocmVnZW4gPT0gIiIgb3IgcmVnZW4gPT0gItGCIiBvciByZWdlbiA9PSAieSIgb3IgcmVnZW4gPT0gInllcyIpCgogICAgYXR0ZW1wdHMgPSAwCiAgICB3aGlsZSBUcnVlOgogICAgICAgIGF0dGVtcHRzICs9IDEKICAgICAgICBncmlkID0gZ2VuZXJhdGVfZmllbGQoTiwgTSwgcCkKICAgICAgICBpZiBleGlzdHNfcGF0aF9iZnMoZ3JpZCk6CiAgICAgICAgICAgIGJyZWFrCiAgICAgICAgaWYgbm90IHJlZ2VuX2ZsYWc6CiAgICAgICAgICAgIGJyZWFrCiAgICAgICAgaWYgYXR0ZW1wdHMgPiAyMDAwOgogICAgICAgICAgICBwcmludCgi0J3QtSDQstC00LDQu9C+0YHRjCDQt9Cz0LXQvdC10YDRg9Cy0LDRgtC4INC/0L7Qu9C1INC3INGI0LvRj9GF0L7QvCDQt9CwINCx0LDQs9Cw0YLQviDRgdC/0YDQvtCxLiDQodC/0YDQvtCx0YPQudGC0LUg0LfQvNGW0L3QuNGC0LggcC4iKQogICAgICAgICAgICByZXR1cm4KCiAgICBwcmludCgiXG7Ql9Cz0LXQvdC10YDQvtCy0LDQvdC1INC/0L7Qu9C1ICjQstC40YDRltCy0L3Rj9C90LUpOiIpCiAgICBwcmludF9ib2FyZF9udW1iZXJlZChncmlkLCBOb25lKQoKICAgIGlmIG5vdCBleGlzdHNfcGF0aF9iZnMoZ3JpZCk6CiAgICAgICAgcHJpbnQoItCo0LvRj9GF0YMg0L3QtdC80LDRlCDigJQg0LfQsNCy0LXRgNGI0YPRji4iKQogICAgICAgIHJldHVybgoKICAgIHByaW50KGYi0J/QvtGH0LjQvdCw0ZTQvNC+INC/0L7RiNGD0Log0L3QsNC50LTQvtCy0YjQvtCz0L4g0L/RgNC+0YHRgtC+0LPQviDRiNC70Y/RhdGDICjRgtCw0LnQvNCw0YPRgiA9IHt0bGltfSDRgdC10LopLi4uIikKICAgIGJlc3QgPSBsb25nZXN0X3BhdGhfZGZzKGdyaWQsIHRpbWVfbGltaXQ9dGxpbSwgcmFuZG9taXplPVRydWUpCgogICAgaWYgbm90IGJlc3Q6CiAgICAgICAgcHJpbnQoItCd0LUg0LfQvdCw0LnQtNC10L3QviDQttC+0LTQvdC+0LPQviDRiNC70Y/RhdGDICjQvdC10L7Rh9GW0LrRg9Cy0LDQvdC+KS4iKQogICAgICAgIHJldHVybgoKICAgICMgYmVzdCDigJQg0YjQu9GP0YUg0Lcg0YHRgtCw0YDRgtGDINC00L4g0YTRltC90ZbRiNGDLCDQv9GA0L7RgdGC0LjQuSwgZ29hbCDQvtGB0YLQsNC90L3RltC5CiAgICBwcmludChmItCX0L3QsNC50LTQtdC90LjQuSDRiNC70Y/RhSDQtNC+0LLQttC40L3QvtGOIHtsZW4oYmVzdCl9ICgwID0g0YHRgtCw0YDRgikuIikKICAgIHByaW50KCJcbtCa0LDRgNGC0LAg0Lcg0L/RgNC+0L3Rg9C80LXRgNC+0LLQsNC90LjQvCDRiNC70Y/RhdC+0Lw6IikKICAgIHByaW50X2JvYXJkX251bWJlcmVkKGdyaWQsIGJlc3QpCgogICAgIyDQlNC+0LTQsNGC0LrQvtCy0L46INCy0LjQstC10LTQtdC80L4g0LrQvtC+0YDQtNC40L3QsNGC0Lgg0YjQu9GP0YXRgyDRgyAxLWJhc2VkCiAgICBwcmludCgiXG7QmtGA0L7QutC4INGI0LvRj9GF0YMgKDEtYmFzZWQg0LrQvtC+0YDQtNC40L3QsNGC0LgpOiIpCiAgICBwcmludChbKHIrMSwgYysxKSBmb3IgKHIsYykgaW4gYmVzdF0pCgppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgogICAgbWFpbigpCg==

MjUKMjUKMC4yNQoxLjUK0YI=

25
25
0.25
1.5
т