Keen Tree Design | MatCom Online Grader

The 2024 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

K - Keen Tree Design

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

<div style="text-align: justify">
You need to design an optimal segment tree to minimize the cost of performing a set of given queries.

**Segment Tree Definition**

A segment tree is a binary tree structure used to efficiently handle range queries on an array. Each node in the segment tree represents a segment with a $start$ and $end$ position such that $start \leq end$. The segments are defined as follows:

1. **Leaf Nodes**: A segment is a leaf node if $start = end$. This node corresponds to a single element in the original array and has no children.
2. **Internal Nodes**: A segment is an internal node if $start < end$. Each internal node has two children:
    - **Left Child**: Represents the left half of the segment.
    - **Right Child**: Represents the right half of the segment.

For an internal node with segment $[start, end]$, we define a pivot position such that $start \leq pivot \leq end$. The segment is split as follows:
- The left child has the range $[start, pivot - 1]$.
- The right child has the range $[pivot, end]$.

**Segment Tree Usage**

A segment tree is useful for efficiently combining consecutive values in an array using an associative operation, such as sum, minimum, or maximum. Each node in the tree stores the combination of all values in its segment. Given a query to combine all values in a subrange $[l, r]$, the following strategy is used:

```python
class Segment:
    left: Segment | None  # Left child of the current segment
    right: Segment | None  # Right child of the current segment
    value: Value           # Combined value of the current segment
    start: int             # Start position of the segment
    pivot: int | None      # Pivot position that splits the segment
    end: int               # End position of the segment

def query(segment: Segment, l: int, r: int) -> Value:
    # Base case: If the query range completely covers the current segment
    if l <= segment.start and segment.end <= r:
        return segment.value

# If the query range falls entirely within the left child
    if r <= segment.pivot:
        return query(segment.left, l, r)

# If the query range falls entirely within the right child
    if segment.pivot < l:
        return query(segment.right, l, r)

# If the query range overlaps both children, combine the results
    left_value = query(segment.left, l, r)
    right_value = query(segment.right, l, r)

value = combine(left_value, right_value)
    return value
```

**Query Costs**

- **Query Cost ($a$)**: Each time the `query` function is called, it incurs a cost of $a$.
- **Combine Cost ($b$)**: Each time two segments are combined using the `combine` function, it incurs a cost of $b$.

**Objective**

You are given the distribution of all queries that will be performed on the segment tree. Your task is to find an optimal segment tree structure that minimizes the total cost of executing all queries.

Input

Output

Sample test(s)

Input

3 1 1 1 2 1 0 1 0

Output

Input

4 3 1 2 3 3 0 3 3 0 2 1 0

Output

174

Input

4 1 3 2 3 3 0 3 3 0 2 1 0

Output

Input

7 6136 5857 6214 4018 8058 3080 6287 3851 3304 5348 6824 6404 9716 8896 2500 989 8076 1781 7817 5476 9121 5170 9887 3427 5176 3254 9828 6479 1984 5251

Output

5126122548

Hints

This is how the optimal tree looks like for the first test case:

![Sample 1](data:image/svg+xml;base64,PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiIHN0YW5kYWxvbmU9Im5vIj8+CjwhRE9DVFlQRSBzdmcgUFVCTElDICItLy9XM0MvL0RURCBTVkcgMS4xLy9FTiIKICAiaHR0cDovL3d3dy53My5vcmcvR3JhcGhpY3MvU1ZHLzEuMS9EVEQvc3ZnMTEuZHRkIj4KPHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGluayIgd2lkdGg9IjQ2MC44cHQiIGhlaWdodD0iMzQ1LjZwdCIgdmlld0JveD0iMCAwIDQ2MC44IDM0NS42IiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHZlcnNpb249IjEuMSI+CiA8bWV0YWRhdGE+CiAgPHJkZjpSREYgeG1sbnM6ZGM9Imh0dHA6Ly9wdXJsLm9yZy9kYy9lbGVtZW50cy8xLjEvIiB4bWxuczpjYz0iaHR0cDovL2NyZWF0aXZlY29tbW9ucy5vcmcvbnMjIiB4bWxuczpyZGY9Imh0dHA6Ly93d3cudzMub3JnLzE5OTkvMDIvMjItcmRmLXN5bnRheC1ucyMiPgogICA8Y2M6V29yaz4KICAgIDxkYzp0eXBlIHJkZjpyZXNvdXJjZT0iaHR0cDovL3B1cmwub3JnL2RjL2RjbWl0eXBlL1N0aWxsSW1hZ2UiLz4KICAgIDxkYzpkYXRlPjIwMjQtMTAtMDNUMTU6MTY6NDMuMTMwMDcwPC9kYzpkYXRlPgogICAgPGRjOmZvcm1hdD5pbWFnZS9zdmcreG1sPC9kYzpmb3JtYXQ+CiAgICA8ZGM6Y3JlYXRvcj4KICAgICA8Y2M6QWdlbnQ+CiAgICAgIDxkYzp0aXRsZT5NYXRwbG90bGliIHYzLjguMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy88L2RjOnRpdGxlPgogICAgIDwvY2M6QWdlbnQ+CiAgICA8L2RjOmNyZWF0b3I+CiAgIDwvY2M6V29yaz4KICA8L3JkZjpSREY+CiA8L21ldGFkYXRhPgogPGRlZnM+CiAgPHN0eWxlIHR5cGU9InRleHQvY3NzIj4qe3N0cm9rZS1saW5lam9pbjogcm91bmQ7IHN0cm9rZS1saW5lY2FwOiBidXR0fTwvc3R5bGU+CiA8L2RlZnM+CiA8ZyBpZD0iZmlndXJlXzEiPgogIDxnIGlkPSJwYXRjaF8xIj4KICAgPHBhdGggZD0iTSAwIDM0NS42IApMIDQ2MC44IDM0NS42IApMIDQ2MC44IDAgCkwgMCAwIAp6CiIgc3R5bGU9ImZpbGw6ICNmZmZmZmYiLz4KICA8L2c+CiAgPGcgaWQ9ImF4ZXNfMSI+CiAgIDxnIGlkPSJMaW5lQ29sbGVjdGlvbl8xIj4KICAgIDxwYXRoIGQ9Ik0gMjkzLjg3MDQzMyAyOS45OTAwODMgCkwgMTY2LjkyNzY0MyAxNzIuOCAKIiBjbGlwLXBhdGg9InVybCgjcGY2ZjMzNWYwNmUpIiBzdHlsZT0iZmlsbDogbm9uZTsgc3Ryb2tlOiAjMDAwMDAwIi8+CiAgICA8cGF0aCBkPSJNIDI5My44NzA0MzMgMjkuOTkwMDgzIApMIDQyMC44MTMyMjMgMTcyLjggCiIgY2xpcC1wYXRoPSJ1cmwoI3BmNmYzMzVmMDZlKSIgc3R5bGU9ImZpbGw6IG5vbmU7IHN0cm9rZTogIzAwMDAwMCIvPgogICAgPHBhdGggZD0iTSAxNjYuOTI3NjQzIDE3Mi44IApMIDM5Ljk4Njc3NyAzMTUuNjA5OTE3IAoiIGNsaXAtcGF0aD0idXJsKCNwZjZmMzM1ZjA2ZSkiIHN0eWxlPSJmaWxsOiBub25lOyBzdHJva2U6ICMwMDAwMDAiLz4KICAgIDxwYXRoIGQ9Ik0gMTY2LjkyNzY0MyAxNzIuOCAKTCAyOTMuODcwNDMzIDMxNS42MDk5MTcgCiIgY2xpcC1wYXRoPSJ1cmwoI3BmNmYzMzVmMDZlKSIgc3R5bGU9ImZpbGw6IG5vbmU7IHN0cm9rZTogIzAwMDAwMCIvPgogICA8L2c+CiAgIDxnIGlkPSJQYXRoQ29sbGVjdGlvbl8xIj4KICAgIDxkZWZzPgogICAgIDxwYXRoIGlkPSJtY2E1Y2M3YWQwYiIgZD0iTSAwIDI3LjM4NjEyOCAKQyA3LjI2Mjg4NiAyNy4zODYxMjggMTQuMjI5MjgxIDI0LjUwMDU1MyAxOS4zNjQ5MTcgMTkuMzY0OTE3IApDIDI0LjUwMDU1MyAxNC4yMjkyODEgMjcuMzg2MTI4IDcuMjYyODg2IDI3LjM4NjEyOCAwIApDIDI3LjM4NjEyOCAtNy4yNjI4ODYgMjQuNTAwNTUzIC0xNC4yMjkyODEgMTkuMzY0OTE3IC0xOS4zNjQ5MTcgCkMgMTQuMjI5MjgxIC0yNC41MDA1NTMgNy4yNjI4ODYgLTI3LjM4NjEyOCAwIC0yNy4zODYxMjggCkMgLTcuMjYyODg2IC0yNy4zODYxMjggLTE0LjIyOTI4MSAtMjQuNTAwNTUzIC0xOS4zNjQ5MTcgLTE5LjM2NDkxNyAKQyAtMjQuNTAwNTUzIC0xNC4yMjkyODEgLTI3LjM4NjEyOCAtNy4yNjI4ODYgLTI3LjM4NjEyOCAwIApDIC0yNy4zODYxMjggNy4yNjI4ODYgLTI0LjUwMDU1MyAxNC4yMjkyODEgLTE5LjM2NDkxNyAxOS4zNjQ5MTcgCkMgLTE0LjIyOTI4MSAyNC41MDA1NTMgLTcuMjYyODg2IDI3LjM4NjEyOCAwIDI3LjM4NjEyOCAKegoiIHN0eWxlPSJzdHJva2U6ICMwMDAwMDAiLz4KICAgIDwvZGVmcz4KICAgIDxnIGNsaXAtcGF0aD0idXJsKCNwZjZmMzM1ZjA2ZSkiPgogICAgIDx1c2UgeGxpbms6aHJlZj0iI21jYTVjYzdhZDBiIiB4PSIyOTMuODcwNDMzIiB5PSIyOS45OTAwODMiIHN0eWxlPSJmaWxsOiAjYWRkOGU2OyBzdHJva2U6ICMwMDAwMDAiLz4KICAgICA8dXNlIHhsaW5rOmhyZWY9IiNtY2E1Y2M3YWQwYiIgeD0iMTY2LjkyNzY0MyIgeT0iMTcyLjgiIHN0eWxlPSJmaWxsOiAjYWRkOGU2OyBzdHJva2U6ICMwMDAwMDAiLz4KICAgICA8dXNlIHhsaW5rOmhyZWY9IiNtY2E1Y2M3YWQwYiIgeD0iNDIwLjgxMzIyMyIgeT0iMTcyLjgiIHN0eWxlPSJmaWxsOiAjYWRkOGU2OyBzdHJva2U6ICMwMDAwMDAiLz4KICAgICA8dXNlIHhsaW5rOmhyZWY9IiNtY2E1Y2M3YWQwYiIgeD0iMzkuOTg2Nzc3IiB5PSIzMTUuNjA5OTE3IiBzdHlsZT0iZmlsbDogI2FkZDhlNjsgc3Ryb2tlOiAjMDAwMDAwIi8+CiAgICAgPHVzZSB4bGluazpocmVmPSIjbWNhNWNjN2FkMGIiIHg9IjI5My44NzA0MzMiIHk9IjMxNS42MDk5MTciIHN0eWxlPSJmaWxsOiAjYWRkOGU2OyBzdHJva2U6ICMwMDAwMDAiLz4KICAgIDwvZz4KICAgPC9nPgogICA8ZyBpZD0idGV4dF8xIj4KICAgIDxnIGNsaXAtcGF0aD0idXJsKCNwZjZmMzM1ZjA2ZSkiPgogICAgIDwhLS0gWzEsIDNdIC0tPgogICAgIDxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDI3OC43MDI0NjUgMzIuNzQ5NDU4KSBzY2FsZSgwLjEgLTAuMSkiPgogICAgICA8ZGVmcz4KICAgICAgIDxwYXRoIGlkPSJEZWphVnVTYW5zLUJvbGQtNWIiIGQ9Ik0gNTUwIDQ4NjMgCkwgMjQ5MSA0ODYzIApMIDI0OTEgNDE1OSAKTCAxNjEzIDQxNTkgCkwgMTYxMyAtMTQxIApMIDI0OTEgLTE0MSAKTCAyNDkxIC04NDQgCkwgNTUwIC04NDQgCkwgNTUwIDQ4NjMgCnoKIiB0cmFuc2Zvcm09InNjYWxlKDAuMDE1NjI1KSIvPgogICAgICAgPHBhdGggaWQ9IkRlamFWdVNhbnMtQm9sZC0zMSIgZD0iTSA3NTAgODMxIApMIDE4MTMgODMxIApMIDE4MTMgMzg0NyAKTCA3MjIgMzYyMiAKTCA3MjIgNDQ0MSAKTCAxODA2IDQ2NjYgCkwgMjk1MCA0NjY2IApMIDI5NTAgODMxIApMIDQwMTMgODMxIApMIDQwMTMgMCAKTCA3NTAgMCAKTCA3NTAgODMxIAp6CiIgdHJhbnNmb3JtPSJzY2FsZSgwLjAxNTYyNSkiLz4KICAgICAgIDxwYXRoIGlkPSJEZWphVnVTYW5zLUJvbGQtMmMiIGQ9Ik0gNjUzIDEyMDkgCkwgMTc3OCAxMjA5IApMIDE3NzggMjU2IApMIDEwMDYgLTkwOSAKTCAzNDEgLTkwOSAKTCA2NTMgMjU2IApMIDY1MyAxMjA5IAp6CiIgdHJhbnNmb3JtPSJzY2FsZSgwLjAxNTYyNSkiLz4KICAgICAgIDxwYXRoIGlkPSJEZWphVnVTYW5zLUJvbGQtMjAiIHRyYW5zZm9ybT0ic2NhbGUoMC4wMTU2MjUpIi8+CiAgICAgICA8cGF0aCBpZD0iRGVqYVZ1U2Fucy1Cb2xkLTMzIiBkPSJNIDI5ODEgMjUxNiAKUSAzNDUzIDIzOTQgMzY5OCAyMDkyIApRIDM5NDQgMTc5MSAzOTQ0IDEzMjUgClEgMzk0NCA2MzEgMzQxMiAyNzAgClEgMjg4MSAtOTEgMTg2MyAtOTEgClEgMTUwMyAtOTEgMTE0MiAtMzMgClEgNzgxIDI1IDQyOCAxNDEgCkwgNDI4IDEwNjkgClEgNzY2IDkwMCAxMDk4IDgxNCAKUSAxNDMxIDcyOCAxNzUzIDcyOCAKUSAyMjMxIDcyOCAyNDg2IDg5MyAKUSAyNzQxIDEwNTkgMjc0MSAxMzY5IApRIDI3NDEgMTY4OCAyNDgwIDE4NTIgClEgMjIxOSAyMDE2IDE3MDkgMjAxNiAKTCAxMjI4IDIwMTYgCkwgMTIyOCAyNzkxIApMIDE3MzQgMjc5MSAKUSAyMTg4IDI3OTEgMjQwOSAyOTMzIApRIDI2MzEgMzA3NSAyNjMxIDMzNjYgClEgMjYzMSAzNjM0IDI0MTUgMzc4MSAKUSAyMjAwIDM5MjggMTgwNiAzOTI4IApRIDE1MTYgMzkyOCAxMjE5IDM4NjIgClEgOTIyIDM3OTcgNjI4IDM2NjkgCkwgNjI4IDQ1NTAgClEgOTg0IDQ2NTAgMTMzNCA0NzAwIApRIDE2ODQgNDc1MCAyMDIyIDQ3NTAgClEgMjkzMSA0NzUwIDMzODIgNDQ1MSAKUSAzODM0IDQxNTMgMzgzNCAzNTUzIApRIDM4MzQgMzE0NCAzNjE4IDI4ODMgClEgMzQwMyAyNjIyIDI5ODEgMjUxNiAKegoiIHRyYW5zZm9ybT0ic2NhbGUoMC4wMTU2MjUpIi8+CiAgICAgICA8cGF0aCBpZD0iRGVqYVZ1U2Fucy1Cb2xkLTVkIiBkPSJNIDIzNzUgLTg0NCAKTCA0MzQgLTg0NCAKTCA0MzQgLTE0MSAKTCAxMzEzIC0xNDEgCkwgMTMxMyA0MTU5IApMIDQzNCA0MTU5IApMIDQzNCA0ODYzIApMIDIzNzUgNDg2MyAKTCAyMzc1IC04NDQgCnoKIiB0cmFuc2Zvcm09InNjYWxlKDAuMDE1NjI1KSIvPgogICAgICA8L2RlZnM+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC01YiIvPgogICAgICA8dXNlIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMzEiIHg9IjQ1LjcwMzEyNSIvPgogICAgICA8dXNlIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMmMiIHg9IjExNS4yODMyMDMiLz4KICAgICAgPHVzZSB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIiB4PSIxNTMuMjcxNDg0Ii8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0zMyIgeD0iMTg4LjA4NTkzOCIvPgogICAgICA8dXNlIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtNWQiIHg9IjI1Ny42NjYwMTYiLz4KICAgICA8L2c+CiAgICA8L2c+CiAgIDwvZz4KICAgPGcgaWQ9InRleHRfMiI+CiAgICA8ZyBjbGlwLXBhdGg9InVybCgjcGY2ZjMzNWYwNmUpIj4KICAgICA8IS0tIFsxLCAyXSAtLT4KICAgICA8ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgxNTEuNzU5Njc1IDE3NS41NTkzNzUpIHNjYWxlKDAuMSAtMC4xKSI+CiAgICAgIDxkZWZzPgogICAgICAgPHBhdGggaWQ9IkRlamFWdVNhbnMtQm9sZC0zMiIgZD0iTSAxODQ0IDg4NCAKTCAzODk3IDg4NCAKTCAzODk3IDAgCkwgNTA2IDAgCkwgNTA2IDg4NCAKTCAyMjA5IDIzODggClEgMjQzOCAyNTk0IDI1NDcgMjc5MSAKUSAyNjU2IDI5ODggMjY1NiAzMjAwIApRIDI2NTYgMzUyOCAyNDM2IDM3MjggClEgMjIxNiAzOTI4IDE4NTAgMzkyOCAKUSAxNTY5IDM5MjggMTIzNCAzODA4IApRIDkwMCAzNjg4IDUxOSAzNDUwIApMIDUxOSA0NDc1IApRIDkyNSA0NjA5IDEzMjIgNDY3OSAKUSAxNzE5IDQ3NTAgMjEwMCA0NzUwIApRIDI5MzggNDc1MCAzNDAyIDQzODEgClEgMzg2NiA0MDEzIDM4NjYgMzM1MyAKUSAzODY2IDI5NzIgMzY2OSAyNjQyIApRIDM0NzIgMjMxMyAyODQxIDE3NTkgCkwgMTg0NCA4ODQgCnoKIiB0cmFuc2Zvcm09InNjYWxlKDAuMDE1NjI1KSIvPgogICAgICA8L2RlZnM+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC01YiIvPgogICAgICA8dXNlIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMzEiIHg9IjQ1LjcwMzEyNSIvPgogICAgICA8dXNlIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMmMiIHg9IjExNS4yODMyMDMiLz4KICAgICAgPHVzZSB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIiB4PSIxNTMuMjcxNDg0Ii8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0zMiIgeD0iMTg4LjA4NTkzOCIvPgogICAgICA8dXNlIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtNWQiIHg9IjI1Ny42NjYwMTYiLz4KICAgICA8L2c+CiAgICA8L2c+CiAgIDwvZz4KICAgPGcgaWQ9InRleHRfMyI+CiAgICA8ZyBjbGlwLXBhdGg9InVybCgjcGY2ZjMzNWYwNmUpIj4KICAgICA8IS0tIFsxLCAxXSAtLT4KICAgICA8ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgyNC44MTg4MDggMzE4LjM2OTI5Mikgc2NhbGUoMC4xIC0wLjEpIj4KICAgICAgPHVzZSB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTViIi8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0zMSIgeD0iNDUuNzAzMTI1Ii8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0yYyIgeD0iMTE1LjI4MzIwMyIvPgogICAgICA8dXNlIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiIHg9IjE1My4yNzE0ODQiLz4KICAgICAgPHVzZSB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTMxIiB4PSIxODguMDg1OTM4Ii8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC01ZCIgeD0iMjU3LjY2NjAxNiIvPgogICAgIDwvZz4KICAgIDwvZz4KICAgPC9nPgogICA8ZyBpZD0idGV4dF80Ij4KICAgIDxnIGNsaXAtcGF0aD0idXJsKCNwZjZmMzM1ZjA2ZSkiPgogICAgIDwhLS0gWzIsIDJdIC0tPgogICAgIDxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDI3OC43MDI0NjUgMzE4LjM2OTI5Mikgc2NhbGUoMC4xIC0wLjEpIj4KICAgICAgPHVzZSB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTViIi8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0zMiIgeD0iNDUuNzAzMTI1Ii8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0yYyIgeD0iMTE1LjI4MzIwMyIvPgogICAgICA8dXNlIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiIHg9IjE1My4yNzE0ODQiLz4KICAgICAgPHVzZSB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTMyIiB4PSIxODguMDg1OTM4Ii8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC01ZCIgeD0iMjU3LjY2NjAxNiIvPgogICAgIDwvZz4KICAgIDwvZz4KICAgPC9nPgogICA8ZyBpZD0idGV4dF81Ij4KICAgIDxnIGNsaXAtcGF0aD0idXJsKCNwZjZmMzM1ZjA2ZSkiPgogICAgIDwhLS0gWzMsIDNdIC0tPgogICAgIDxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDQwNS42NDUyNTQgMTc1LjU1OTM3NSkgc2NhbGUoMC4xIC0wLjEpIj4KICAgICAgPHVzZSB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTViIi8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0zMyIgeD0iNDUuNzAzMTI1Ii8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0yYyIgeD0iMTE1LjI4MzIwMyIvPgogICAgICA8dXNlIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiIHg9IjE1My4yNzE0ODQiLz4KICAgICAgPHVzZSB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTMzIiB4PSIxODguMDg1OTM4Ii8+CiAgICAgIDx1c2UgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC01ZCIgeD0iMjU3LjY2NjAxNiIvPgogICAgIDwvZz4KICAgIDwvZz4KICAgPC9nPgogIDwvZz4KIDwvZz4KIDxkZWZzPgogIDxjbGlwUGF0aCBpZD0icGY2ZjMzNWYwNmUiPgogICA8cmVjdCB4PSIwIiB5PSIwIiB3aWR0aD0iNDYwLjgiIGhlaWdodD0iMzQ1LjYiLz4KICA8L2NsaXBQYXRoPgogPC9kZWZzPgo8L3N2Zz4K)

In this test case the queries are $([1,1], [1, 2], [1, 2], [1, 3], [2, 3])$. In this scenario both the cost of calling $query$ and $combine$ is 1, so the total cost is the number of times each method was called. The cost for each individual query is the following:
- **$[1, 1]$**: Query nodes $[1, 3], [1, 2], [1, 1]$. $Cost = 3$.
- **$[1, 2]$**: Query nodes $[1, 3], [1, 2]$. $Cost = 2$.
- **$[1, 2]$**: Query nodes $[1, 3], [1, 2]$. $Cost = 2$.
- **$[1, 3]$**: Query nodes $[1, 3]$. $Cost = 1$.
- **$[2, 3]$**: Query nodes $[1, 3], [1, 2], [2, 2], [3, 3]$, Combine the result on node $[1, 3]$. $Cost = 5$.

The total cost is: $3 + 2 + 2 + 1 + 5 = 13$

The optimal tree for the next test cases is:

**Second test case**

![Sample 2](data:image/svg+xml;base64,PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iVVRGLTgiPz4KPCFET0NUWVBFIHN2ZyAgUFVCTElDICctLy9XM0MvL0RURCBTVkcgMS4xLy9FTicgICdodHRwOi8vd3d3LnczLm9yZy9HcmFwaGljcy9TVkcvMS4xL0RURC9zdmcxMS5kdGQnPgo8c3ZnIHdpZHRoPSI0NjAuOHB0IiBoZWlnaHQ9IjM0NS42cHQiIHZlcnNpb249IjEuMSIgdmlld0JveD0iMCAwIDQ2MC44IDM0NS42IiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHhtbG5zOnhsaW5rPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5L3hsaW5rIj4KPG1ldGFkYXRhPgo8cmRmOlJERiB4bWxuczpjYz0iaHR0cDovL2NyZWF0aXZlY29tbW9ucy5vcmcvbnMjIiB4bWxuczpkYz0iaHR0cDovL3B1cmwub3JnL2RjL2VsZW1lbnRzLzEuMS8iIHhtbG5zOnJkZj0iaHR0cDovL3d3dy53My5vcmcvMTk5OS8wMi8yMi1yZGYtc3ludGF4LW5zIyI+CjxjYzpXb3JrPgo8ZGM6dHlwZSByZGY6cmVzb3VyY2U9Imh0dHA6Ly9wdXJsLm9yZy9kYy9kY21pdHlwZS9TdGlsbEltYWdlIi8+CjxkYzpkYXRlPjIwMjQtMTAtMDNUMTU6MDc6MzIuMTA1NDIwPC9kYzpkYXRlPgo8ZGM6Zm9ybWF0PmltYWdlL3N2Zyt4bWw8L2RjOmZvcm1hdD4KPGRjOmNyZWF0b3I+CjxjYzpBZ2VudD4KPGRjOnRpdGxlPk1hdHBsb3RsaWIgdjMuOC4zLCBodHRwczovL21hdHBsb3RsaWIub3JnLzwvZGM6dGl0bGU+CjwvY2M6QWdlbnQ+CjwvZGM6Y3JlYXRvcj4KPC9jYzpXb3JrPgo8L3JkZjpSREY+CjwvbWV0YWRhdGE+CjxkZWZzPgo8c3R5bGUgdHlwZT0idGV4dC9jc3MiPip7c3Ryb2tlLWxpbmVqb2luOiByb3VuZDsgc3Ryb2tlLWxpbmVjYXA6IGJ1dHR9PC9zdHlsZT4KPC9kZWZzPgo8cGF0aCBkPSJtMCAzNDUuNmg0NjAuOHYtMzQ1LjZoLTQ2MC44eiIgZmlsbD0iI2ZmZiIvPgo8ZyBmaWxsPSJub25lIiBzdHJva2U9IiMwMDAiPgo8cGF0aCBkPSJtMjMwLjQgMjkuOTktNjMuNDcxIDE0Mi44MSIgY2xpcC1wYXRoPSJ1cmwoI2EpIi8+CjxwYXRoIGQ9Im0yMzAuNCAyOS45OSA2My40NzEgMTQyLjgxIiBjbGlwLXBhdGg9InVybCgjYSkiLz4KPHBhdGggZD0ibTE2Ni45MyAxNzIuOC0xMjYuOTQgMTQyLjgxIiBjbGlwLXBhdGg9InVybCgjYSkiLz4KPHBhdGggZD0ibTE2Ni45MyAxNzIuOHYxNDIuODEiIGNsaXAtcGF0aD0idXJsKCNhKSIvPgo8cGF0aCBkPSJtMjkzLjg3IDE3Mi44djE0Mi44MSIgY2xpcC1wYXRoPSJ1cmwoI2EpIi8+CjxwYXRoIGQ9Im0yOTMuODcgMTcyLjggMTI2Ljk0IDE0Mi44MSIgY2xpcC1wYXRoPSJ1cmwoI2EpIi8+CjwvZz4KPGRlZnM+CjxwYXRoIGlkPSJiIiBkPSJtMCAyNy4zODZjNy4yNjI5IDAgMTQuMjI5LTIuODg1NiAxOS4zNjUtOC4wMjEyczguMDIxMi0xMi4xMDIgOC4wMjEyLTE5LjM2NS0yLjg4NTYtMTQuMjI5LTguMDIxMi0xOS4zNjUtMTIuMTAyLTguMDIxMi0xOS4zNjUtOC4wMjEyLTE0LjIyOSAyLjg4NTYtMTkuMzY1IDguMDIxMi04LjAyMTIgMTIuMTAyLTguMDIxMiAxOS4zNjUgMi44ODU2IDE0LjIyOSA4LjAyMTIgMTkuMzY1IDEyLjEwMiA4LjAyMTIgMTkuMzY1IDguMDIxMnoiIHN0cm9rZT0iIzAwMCIvPgo8L2RlZnM+CjxnIGNsaXAtcGF0aD0idXJsKCNhKSIgZmlsbD0iI2FkZDhlNiIgc3Ryb2tlPSIjMDAwMDAwIj4KPHVzZSB4PSIyMzAuMzk5NTE5IiB5PSIyOS45OTAwODMiIHhsaW5rOmhyZWY9IiNiIi8+Cjx1c2UgeD0iMTY2LjkyODI4NCIgeT0iMTcyLjgiIHhsaW5rOmhyZWY9IiNiIi8+Cjx1c2UgeD0iMjkzLjg3MDc1NCIgeT0iMTcyLjgiIHhsaW5rOmhyZWY9IiNiIi8+Cjx1c2UgeD0iMzkuOTg2Nzc3IiB5PSIzMTUuNjA5OTE3IiB4bGluazpocmVmPSIjYiIvPgo8dXNlIHg9IjE2Ni45MjgyODQiIHk9IjMxNS42MDk5MTciIHhsaW5rOmhyZWY9IiNiIi8+Cjx1c2UgeD0iMjkzLjg3MDc1NCIgeT0iMzE1LjYwOTkxNyIgeGxpbms6aHJlZj0iI2IiLz4KPHVzZSB4PSI0MjAuODEzMjIzIiB5PSIzMTUuNjA5OTE3IiB4bGluazpocmVmPSIjYiIvPgo8L2c+CjxnIGNsaXAtcGF0aD0idXJsKCNhKSI+CjxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDIxNS4yMyAzMi43NDkpIHNjYWxlKC4xIC0uMSkiPgo8ZGVmcz4KPHBhdGggaWQ9ImQiIHRyYW5zZm9ybT0ic2NhbGUoLjAxNTYyNSkiIGQ9Im01NTAgNDg2M2gxOTQxdi03MDRoLTg3OHYtNDMwMGg4Nzh2LTcwM2gtMTk0MXY1NzA3eiIvPgo8cGF0aCBpZD0iZyIgdHJhbnNmb3JtPSJzY2FsZSguMDE1NjI1KSIgZD0ibTc1MCA4MzFoMTA2M3YzMDE2bC0xMDkxLTIyNXY4MTlsMTA4NCAyMjVoMTE0NHYtMzgzNWgxMDYzdi04MzFoLTMyNjN2ODMxeiIvPgo8cGF0aCBpZD0iZSIgdHJhbnNmb3JtPSJzY2FsZSguMDE1NjI1KSIgZD0ibTY1MyAxMjA5aDExMjV2LTk1M2wtNzcyLTExNjVoLTY2NWwzMTIgMTE2NXY5NTN6Ii8+CjxwYXRoIGlkPSJmIiB0cmFuc2Zvcm09InNjYWxlKC4wMTU2MjUpIiBkPSJtMjM1NiAzNjc1LTEzMTgtMTk1M2gxMzE4djE5NTN6bS0yMDAgOTkxaDEzMzh2LTI5NDRoNjY1di04NzJoLTY2NXYtODUwaC0xMTM4djg1MGgtMjA2OHYxMDMxbDE4NjggMjc4NXoiLz4KPHBhdGggaWQ9ImMiIHRyYW5zZm9ybT0ic2NhbGUoLjAxNTYyNSkiIGQ9Im0yMzc1LTg0NGgtMTk0MXY3MDNoODc5djQzMDBoLTg3OXY3MDRoMTk0MXYtNTcwN3oiLz4KPC9kZWZzPgo8dXNlIHhsaW5rOmhyZWY9IiNkIi8+Cjx1c2UgeD0iNDUuNzAzMTI1IiB4bGluazpocmVmPSIjZyIvPgo8dXNlIHg9IjExNS4yODMyMDMiIHhsaW5rOmhyZWY9IiNlIi8+Cjx1c2UgeD0iMTUzLjI3MTQ4NCIgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0yMCIvPgo8dXNlIHg9IjE4OC4wODU5MzgiIHhsaW5rOmhyZWY9IiNmIi8+Cjx1c2UgeD0iMjU3LjY2NjAxNiIgeGxpbms6aHJlZj0iI2MiLz4KPC9nPgo8L2c+CjxnIGNsaXAtcGF0aD0idXJsKCNhKSI+CjxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDE1MS43NiAxNzUuNTYpIHNjYWxlKC4xIC0uMSkiPgo8ZGVmcz4KPHBhdGggaWQ9ImkiIHRyYW5zZm9ybT0ic2NhbGUoLjAxNTYyNSkiIGQ9Im0xODQ0IDg4NGgyMDUzdi04ODRoLTMzOTF2ODg0bDE3MDMgMTUwNHEyMjkgMjA2IDMzOCA0MDN0MTA5IDQwOXEwIDMyOC0yMjAgNTI4dC01ODYgMjAwcS0yODEgMC02MTYtMTIwLTMzNC0xMjAtNzE1LTM1OHYxMDI1cTQwNiAxMzQgODAzIDIwNCAzOTcgNzEgNzc4IDcxIDgzOCAwIDEzMDItMzY5IDQ2NC0zNjggNDY0LTEwMjggMC0zODEtMTk3LTcxMS0xOTctMzI5LTgyOC04ODNsLTk5Ny04NzV6Ii8+CjwvZGVmcz4KPHVzZSB4bGluazpocmVmPSIjZCIvPgo8dXNlIHg9IjQ1LjcwMzEyNSIgeGxpbms6aHJlZj0iI2ciLz4KPHVzZSB4PSIxMTUuMjgzMjAzIiB4bGluazpocmVmPSIjZSIvPgo8dXNlIHg9IjE1My4yNzE0ODQiIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiLz4KPHVzZSB4PSIxODguMDg1OTM4IiB4bGluazpocmVmPSIjaSIvPgo8dXNlIHg9IjI1Ny42NjYwMTYiIHhsaW5rOmhyZWY9IiNjIi8+CjwvZz4KPC9nPgo8ZyBjbGlwLXBhdGg9InVybCgjYSkiPgo8ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgyNC44MTkgMzE4LjM3KSBzY2FsZSguMSAtLjEpIj4KPHVzZSB4bGluazpocmVmPSIjZCIvPgo8dXNlIHg9IjQ1LjcwMzEyNSIgeGxpbms6aHJlZj0iI2ciLz4KPHVzZSB4PSIxMTUuMjgzMjAzIiB4bGluazpocmVmPSIjZSIvPgo8dXNlIHg9IjE1My4yNzE0ODQiIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiLz4KPHVzZSB4PSIxODguMDg1OTM4IiB4bGluazpocmVmPSIjZyIvPgo8dXNlIHg9IjI1Ny42NjYwMTYiIHhsaW5rOmhyZWY9IiNjIi8+CjwvZz4KPC9nPgo8ZyBjbGlwLXBhdGg9InVybCgjYSkiPgo8ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgxNTEuNzYgMzE4LjM3KSBzY2FsZSguMSAtLjEpIj4KPHVzZSB4bGluazpocmVmPSIjZCIvPgo8dXNlIHg9IjQ1LjcwMzEyNSIgeGxpbms6aHJlZj0iI2kiLz4KPHVzZSB4PSIxMTUuMjgzMjAzIiB4bGluazpocmVmPSIjZSIvPgo8dXNlIHg9IjE1My4yNzE0ODQiIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiLz4KPHVzZSB4PSIxODguMDg1OTM4IiB4bGluazpocmVmPSIjaSIvPgo8dXNlIHg9IjI1Ny42NjYwMTYiIHhsaW5rOmhyZWY9IiNjIi8+CjwvZz4KPC9nPgo8ZyBjbGlwLXBhdGg9InVybCgjYSkiPgo8ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgyNzguNyAxNzUuNTYpIHNjYWxlKC4xIC0uMSkiPgo8ZGVmcz4KPHBhdGggaWQ9ImgiIHRyYW5zZm9ybT0ic2NhbGUoLjAxNTYyNSkiIGQ9Im0yOTgxIDI1MTZxNDcyLTEyMiA3MTctNDI0IDI0Ni0zMDEgMjQ2LTc2NyAwLTY5NC01MzItMTA1NS01MzEtMzYxLTE1NDktMzYxLTM2MCAwLTcyMSA1OHQtNzE0IDE3NHY5MjhxMzM4LTE2OSA2NzAtMjU1IDMzMy04NiA2NTUtODYgNDc4IDAgNzMzIDE2NSAyNTUgMTY2IDI1NSA0NzYgMCAzMTktMjYxIDQ4M3QtNzcxIDE2NGgtNDgxdjc3NWg1MDZxNDU0IDAgNjc1IDE0MiAyMjIgMTQyIDIyMiA0MzMgMCAyNjgtMjE2IDQxNS0yMTUgMTQ3LTYwOSAxNDctMjkwIDAtNTg3LTY2LTI5Ny02NS01OTEtMTkzdjg4MXEzNTYgMTAwIDcwNiAxNTB0Njg4IDUwcTkwOSAwIDEzNjAtMjk5IDQ1Mi0yOTggNDUyLTg5OCAwLTQwOS0yMTYtNjcwLTIxNS0yNjEtNjM3LTM2N3oiLz4KPC9kZWZzPgo8dXNlIHhsaW5rOmhyZWY9IiNkIi8+Cjx1c2UgeD0iNDUuNzAzMTI1IiB4bGluazpocmVmPSIjaCIvPgo8dXNlIHg9IjExNS4yODMyMDMiIHhsaW5rOmhyZWY9IiNlIi8+Cjx1c2UgeD0iMTUzLjI3MTQ4NCIgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0yMCIvPgo8dXNlIHg9IjE4OC4wODU5MzgiIHhsaW5rOmhyZWY9IiNmIi8+Cjx1c2UgeD0iMjU3LjY2NjAxNiIgeGxpbms6aHJlZj0iI2MiLz4KPC9nPgo8L2c+CjxnIGNsaXAtcGF0aD0idXJsKCNhKSI+CjxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDI3OC43IDMxOC4zNykgc2NhbGUoLjEgLS4xKSI+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNoIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2giLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIj4KPGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoNDA1LjY1IDMxOC4zNykgc2NhbGUoLjEgLS4xKSI+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNmIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2YiLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGRlZnM+CjxjbGlwUGF0aCBpZD0iYSI+CjxyZWN0IHdpZHRoPSI0NjAuOCIgaGVpZ2h0PSIzNDUuNiIvPgo8L2NsaXBQYXRoPgo8L2RlZnM+Cjwvc3ZnPgoK)

**Third test case**

![Sample 3](data:image/svg+xml;base64,PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iVVRGLTgiPz4KPCFET0NUWVBFIHN2ZyAgUFVCTElDICctLy9XM0MvL0RURCBTVkcgMS4xLy9FTicgICdodHRwOi8vd3d3LnczLm9yZy9HcmFwaGljcy9TVkcvMS4xL0RURC9zdmcxMS5kdGQnPgo8c3ZnIHdpZHRoPSI0NjAuOHB0IiBoZWlnaHQ9IjM0NS42cHQiIHZlcnNpb249IjEuMSIgdmlld0JveD0iMCAwIDQ2MC44IDM0NS42IiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHhtbG5zOnhsaW5rPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5L3hsaW5rIj4KPG1ldGFkYXRhPgo8cmRmOlJERiB4bWxuczpjYz0iaHR0cDovL2NyZWF0aXZlY29tbW9ucy5vcmcvbnMjIiB4bWxuczpkYz0iaHR0cDovL3B1cmwub3JnL2RjL2VsZW1lbnRzLzEuMS8iIHhtbG5zOnJkZj0iaHR0cDovL3d3dy53My5vcmcvMTk5OS8wMi8yMi1yZGYtc3ludGF4LW5zIyI+CjxjYzpXb3JrPgo8ZGM6dHlwZSByZGY6cmVzb3VyY2U9Imh0dHA6Ly9wdXJsLm9yZy9kYy9kY21pdHlwZS9TdGlsbEltYWdlIi8+CjxkYzpkYXRlPjIwMjQtMTAtMDNUMTU6MDc6MzUuNTE4MTU1PC9kYzpkYXRlPgo8ZGM6Zm9ybWF0PmltYWdlL3N2Zyt4bWw8L2RjOmZvcm1hdD4KPGRjOmNyZWF0b3I+CjxjYzpBZ2VudD4KPGRjOnRpdGxlPk1hdHBsb3RsaWIgdjMuOC4zLCBodHRwczovL21hdHBsb3RsaWIub3JnLzwvZGM6dGl0bGU+CjwvY2M6QWdlbnQ+CjwvZGM6Y3JlYXRvcj4KPC9jYzpXb3JrPgo8L3JkZjpSREY+CjwvbWV0YWRhdGE+CjxkZWZzPgo8c3R5bGUgdHlwZT0idGV4dC9jc3MiPip7c3Ryb2tlLWxpbmVqb2luOiByb3VuZDsgc3Ryb2tlLWxpbmVjYXA6IGJ1dHR9PC9zdHlsZT4KPC9kZWZzPgo8cGF0aCBkPSJtMCAzNDUuNmg0NjAuOHYtMzQ1LjZoLTQ2MC44eiIgZmlsbD0iI2ZmZiIvPgo8ZyBmaWxsPSJub25lIiBzdHJva2U9IiMwMDAiPgo8cGF0aCBkPSJtMzI1LjYxIDI5Ljk5LTk1LjIwNyA5NS4yMDciIGNsaXAtcGF0aD0idXJsKCNhKSIvPgo8cGF0aCBkPSJtMzI1LjYxIDI5Ljk5IDk1LjIwNyA5NS4yMDciIGNsaXAtcGF0aD0idXJsKCNhKSIvPgo8cGF0aCBkPSJtMjMwLjQgMTI1LjItOTUuMjA3IDk1LjIwNyIgY2xpcC1wYXRoPSJ1cmwoI2EpIi8+CjxwYXRoIGQ9Im0yMzAuNCAxMjUuMiA5NS4yMDcgOTUuMjA3IiBjbGlwLXBhdGg9InVybCgjYSkiLz4KPHBhdGggZD0ibTEzNS4xOSAyMjAuNC05NS4yMDYgOTUuMjA3IiBjbGlwLXBhdGg9InVybCgjYSkiLz4KPHBhdGggZD0ibTEzNS4xOSAyMjAuNCA5NS4yMDcgOTUuMjA3IiBjbGlwLXBhdGg9InVybCgjYSkiLz4KPC9nPgo8ZGVmcz4KPHBhdGggaWQ9ImIiIGQ9Im0wIDI3LjM4NmM3LjI2MjkgMCAxNC4yMjktMi44ODU2IDE5LjM2NS04LjAyMTJzOC4wMjEyLTEyLjEwMiA4LjAyMTItMTkuMzY1LTIuODg1Ni0xNC4yMjktOC4wMjEyLTE5LjM2NS0xMi4xMDItOC4wMjEyLTE5LjM2NS04LjAyMTItMTQuMjI5IDIuODg1Ni0xOS4zNjUgOC4wMjEyLTguMDIxMiAxMi4xMDItOC4wMjEyIDE5LjM2NSAyLjg4NTYgMTQuMjI5IDguMDIxMiAxOS4zNjUgMTIuMTAyIDguMDIxMiAxOS4zNjUgOC4wMjEyeiIgc3Ryb2tlPSIjMDAwIi8+CjwvZGVmcz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIiBmaWxsPSIjYWRkOGU2IiBzdHJva2U9IiMwMDAwMDAiPgo8dXNlIHg9IjMyNS42MDYyNTEiIHk9IjI5Ljk5MDA4MyIgeGxpbms6aHJlZj0iI2IiLz4KPHVzZSB4PSIyMzAuMzk5Mjc5IiB5PSIxMjUuMTk2Njk0IiB4bGluazpocmVmPSIjYiIvPgo8dXNlIHg9IjQyMC44MTMyMjMiIHk9IjEyNS4xOTY2OTQiIHhsaW5rOmhyZWY9IiNiIi8+Cjx1c2UgeD0iMTM1LjE5MjMwNyIgeT0iMjIwLjQwMzMwNiIgeGxpbms6aHJlZj0iI2IiLz4KPHVzZSB4PSIzMjUuNjA2MjUxIiB5PSIyMjAuNDAzMzA2IiB4bGluazpocmVmPSIjYiIvPgo8dXNlIHg9IjM5Ljk4Njc3NyIgeT0iMzE1LjYwOTkxNyIgeGxpbms6aHJlZj0iI2IiLz4KPHVzZSB4PSIyMzAuMzk5Mjc5IiB5PSIzMTUuNjA5OTE3IiB4bGluazpocmVmPSIjYiIvPgo8L2c+CjxnIGNsaXAtcGF0aD0idXJsKCNhKSI+CjxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDMxMC40NCAzMi43NDkpIHNjYWxlKC4xIC0uMSkiPgo8ZGVmcz4KPHBhdGggaWQ9ImQiIHRyYW5zZm9ybT0ic2NhbGUoLjAxNTYyNSkiIGQ9Im01NTAgNDg2M2gxOTQxdi03MDRoLTg3OHYtNDMwMGg4Nzh2LTcwM2gtMTk0MXY1NzA3eiIvPgo8cGF0aCBpZD0iZiIgdHJhbnNmb3JtPSJzY2FsZSguMDE1NjI1KSIgZD0ibTc1MCA4MzFoMTA2M3YzMDE2bC0xMDkxLTIyNXY4MTlsMTA4NCAyMjVoMTE0NHYtMzgzNWgxMDYzdi04MzFoLTMyNjN2ODMxeiIvPgo8cGF0aCBpZD0iZSIgdHJhbnNmb3JtPSJzY2FsZSguMDE1NjI1KSIgZD0ibTY1MyAxMjA5aDExMjV2LTk1M2wtNzcyLTExNjVoLTY2NWwzMTIgMTE2NXY5NTN6Ii8+CjxwYXRoIGlkPSJnIiB0cmFuc2Zvcm09InNjYWxlKC4wMTU2MjUpIiBkPSJtMjM1NiAzNjc1LTEzMTgtMTk1M2gxMzE4djE5NTN6bS0yMDAgOTkxaDEzMzh2LTI5NDRoNjY1di04NzJoLTY2NXYtODUwaC0xMTM4djg1MGgtMjA2OHYxMDMxbDE4NjggMjc4NXoiLz4KPHBhdGggaWQ9ImMiIHRyYW5zZm9ybT0ic2NhbGUoLjAxNTYyNSkiIGQ9Im0yMzc1LTg0NGgtMTk0MXY3MDNoODc5djQzMDBoLTg3OXY3MDRoMTk0MXYtNTcwN3oiLz4KPC9kZWZzPgo8dXNlIHhsaW5rOmhyZWY9IiNkIi8+Cjx1c2UgeD0iNDUuNzAzMTI1IiB4bGluazpocmVmPSIjZiIvPgo8dXNlIHg9IjExNS4yODMyMDMiIHhsaW5rOmhyZWY9IiNlIi8+Cjx1c2UgeD0iMTUzLjI3MTQ4NCIgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0yMCIvPgo8dXNlIHg9IjE4OC4wODU5MzgiIHhsaW5rOmhyZWY9IiNnIi8+Cjx1c2UgeD0iMjU3LjY2NjAxNiIgeGxpbms6aHJlZj0iI2MiLz4KPC9nPgo8L2c+CjxnIGNsaXAtcGF0aD0idXJsKCNhKSI+CjxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDIxNS4yMyAxMjcuOTYpIHNjYWxlKC4xIC0uMSkiPgo8ZGVmcz4KPHBhdGggaWQ9ImgiIHRyYW5zZm9ybT0ic2NhbGUoLjAxNTYyNSkiIGQ9Im0yOTgxIDI1MTZxNDcyLTEyMiA3MTctNDI0IDI0Ni0zMDEgMjQ2LTc2NyAwLTY5NC01MzItMTA1NS01MzEtMzYxLTE1NDktMzYxLTM2MCAwLTcyMSA1OHQtNzE0IDE3NHY5MjhxMzM4LTE2OSA2NzAtMjU1IDMzMy04NiA2NTUtODYgNDc4IDAgNzMzIDE2NSAyNTUgMTY2IDI1NSA0NzYgMCAzMTktMjYxIDQ4M3QtNzcxIDE2NGgtNDgxdjc3NWg1MDZxNDU0IDAgNjc1IDE0MiAyMjIgMTQyIDIyMiA0MzMgMCAyNjgtMjE2IDQxNS0yMTUgMTQ3LTYwOSAxNDctMjkwIDAtNTg3LTY2LTI5Ny02NS01OTEtMTkzdjg4MXEzNTYgMTAwIDcwNiAxNTB0Njg4IDUwcTkwOSAwIDEzNjAtMjk5IDQ1Mi0yOTggNDUyLTg5OCAwLTQwOS0yMTYtNjcwLTIxNS0yNjEtNjM3LTM2N3oiLz4KPC9kZWZzPgo8dXNlIHhsaW5rOmhyZWY9IiNkIi8+Cjx1c2UgeD0iNDUuNzAzMTI1IiB4bGluazpocmVmPSIjZiIvPgo8dXNlIHg9IjExNS4yODMyMDMiIHhsaW5rOmhyZWY9IiNlIi8+Cjx1c2UgeD0iMTUzLjI3MTQ4NCIgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0yMCIvPgo8dXNlIHg9IjE4OC4wODU5MzgiIHhsaW5rOmhyZWY9IiNoIi8+Cjx1c2UgeD0iMjU3LjY2NjAxNiIgeGxpbms6aHJlZj0iI2MiLz4KPC9nPgo8L2c+CjxnIGNsaXAtcGF0aD0idXJsKCNhKSI+CjxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDEyMC4wMiAyMjMuMTYpIHNjYWxlKC4xIC0uMSkiPgo8ZGVmcz4KPHBhdGggaWQ9ImkiIHRyYW5zZm9ybT0ic2NhbGUoLjAxNTYyNSkiIGQ9Im0xODQ0IDg4NGgyMDUzdi04ODRoLTMzOTF2ODg0bDE3MDMgMTUwNHEyMjkgMjA2IDMzOCA0MDN0MTA5IDQwOXEwIDMyOC0yMjAgNTI4dC01ODYgMjAwcS0yODEgMC02MTYtMTIwLTMzNC0xMjAtNzE1LTM1OHYxMDI1cTQwNiAxMzQgODAzIDIwNCAzOTcgNzEgNzc4IDcxIDgzOCAwIDEzMDItMzY5IDQ2NC0zNjggNDY0LTEwMjggMC0zODEtMTk3LTcxMS0xOTctMzI5LTgyOC04ODNsLTk5Ny04NzV6Ii8+CjwvZGVmcz4KPHVzZSB4bGluazpocmVmPSIjZCIvPgo8dXNlIHg9IjQ1LjcwMzEyNSIgeGxpbms6aHJlZj0iI2YiLz4KPHVzZSB4PSIxMTUuMjgzMjAzIiB4bGluazpocmVmPSIjZSIvPgo8dXNlIHg9IjE1My4yNzE0ODQiIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiLz4KPHVzZSB4PSIxODguMDg1OTM4IiB4bGluazpocmVmPSIjaSIvPgo8dXNlIHg9IjI1Ny42NjYwMTYiIHhsaW5rOmhyZWY9IiNjIi8+CjwvZz4KPC9nPgo8ZyBjbGlwLXBhdGg9InVybCgjYSkiPgo8ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgyNC44MTkgMzE4LjM3KSBzY2FsZSguMSAtLjEpIj4KPHVzZSB4bGluazpocmVmPSIjZCIvPgo8dXNlIHg9IjQ1LjcwMzEyNSIgeGxpbms6aHJlZj0iI2YiLz4KPHVzZSB4PSIxMTUuMjgzMjAzIiB4bGluazpocmVmPSIjZSIvPgo8dXNlIHg9IjE1My4yNzE0ODQiIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiLz4KPHVzZSB4PSIxODguMDg1OTM4IiB4bGluazpocmVmPSIjZiIvPgo8dXNlIHg9IjI1Ny42NjYwMTYiIHhsaW5rOmhyZWY9IiNjIi8+CjwvZz4KPC9nPgo8ZyBjbGlwLXBhdGg9InVybCgjYSkiPgo8ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgyMTUuMjMgMzE4LjM3KSBzY2FsZSguMSAtLjEpIj4KPHVzZSB4bGluazpocmVmPSIjZCIvPgo8dXNlIHg9IjQ1LjcwMzEyNSIgeGxpbms6aHJlZj0iI2kiLz4KPHVzZSB4PSIxMTUuMjgzMjAzIiB4bGluazpocmVmPSIjZSIvPgo8dXNlIHg9IjE1My4yNzE0ODQiIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiLz4KPHVzZSB4PSIxODguMDg1OTM4IiB4bGluazpocmVmPSIjaSIvPgo8dXNlIHg9IjI1Ny42NjYwMTYiIHhsaW5rOmhyZWY9IiNjIi8+CjwvZz4KPC9nPgo8ZyBjbGlwLXBhdGg9InVybCgjYSkiPgo8ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgzMTAuNDQgMjIzLjE2KSBzY2FsZSguMSAtLjEpIj4KPHVzZSB4bGluazpocmVmPSIjZCIvPgo8dXNlIHg9IjQ1LjcwMzEyNSIgeGxpbms6aHJlZj0iI2giLz4KPHVzZSB4PSIxMTUuMjgzMjAzIiB4bGluazpocmVmPSIjZSIvPgo8dXNlIHg9IjE1My4yNzE0ODQiIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiLz4KPHVzZSB4PSIxODguMDg1OTM4IiB4bGluazpocmVmPSIjaCIvPgo8dXNlIHg9IjI1Ny42NjYwMTYiIHhsaW5rOmhyZWY9IiNjIi8+CjwvZz4KPC9nPgo8ZyBjbGlwLXBhdGg9InVybCgjYSkiPgo8ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSg0MDUuNjUgMTI3Ljk2KSBzY2FsZSguMSAtLjEpIj4KPHVzZSB4bGluazpocmVmPSIjZCIvPgo8dXNlIHg9IjQ1LjcwMzEyNSIgeGxpbms6aHJlZj0iI2ciLz4KPHVzZSB4PSIxMTUuMjgzMjAzIiB4bGluazpocmVmPSIjZSIvPgo8dXNlIHg9IjE1My4yNzE0ODQiIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiLz4KPHVzZSB4PSIxODguMDg1OTM4IiB4bGluazpocmVmPSIjZyIvPgo8dXNlIHg9IjI1Ny42NjYwMTYiIHhsaW5rOmhyZWY9IiNjIi8+CjwvZz4KPC9nPgo8ZGVmcz4KPGNsaXBQYXRoIGlkPSJhIj4KPHJlY3Qgd2lkdGg9IjQ2MC44IiBoZWlnaHQ9IjM0NS42Ii8+CjwvY2xpcFBhdGg+CjwvZGVmcz4KPC9zdmc+Cg==)

**Fourth test case**

![Sample 4](data:image/svg+xml;base64,PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iVVRGLTgiPz4KPCFET0NUWVBFIHN2ZyAgUFVCTElDICctLy9XM0MvL0RURCBTVkcgMS4xLy9FTicgICdodHRwOi8vd3d3LnczLm9yZy9HcmFwaGljcy9TVkcvMS4xL0RURC9zdmcxMS5kdGQnPgo8c3ZnIHdpZHRoPSI0NjAuOHB0IiBoZWlnaHQ9IjM0NS42cHQiIHZlcnNpb249IjEuMSIgdmlld0JveD0iMCAwIDQ2MC44IDM0NS42IiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHhtbG5zOnhsaW5rPSJodHRwOi8vd3d3LnczLm9yZy8xOTk5L3hsaW5rIj4KPG1ldGFkYXRhPgo8cmRmOlJERiB4bWxuczpjYz0iaHR0cDovL2NyZWF0aXZlY29tbW9ucy5vcmcvbnMjIiB4bWxuczpkYz0iaHR0cDovL3B1cmwub3JnL2RjL2VsZW1lbnRzLzEuMS8iIHhtbG5zOnJkZj0iaHR0cDovL3d3dy53My5vcmcvMTk5OS8wMi8yMi1yZGYtc3ludGF4LW5zIyI+CjxjYzpXb3JrPgo8ZGM6dHlwZSByZGY6cmVzb3VyY2U9Imh0dHA6Ly9wdXJsLm9yZy9kYy9kY21pdHlwZS9TdGlsbEltYWdlIi8+CjxkYzpkYXRlPjIwMjQtMTAtMDNUMTU6MDc6MzguNTIxNDY4PC9kYzpkYXRlPgo8ZGM6Zm9ybWF0PmltYWdlL3N2Zyt4bWw8L2RjOmZvcm1hdD4KPGRjOmNyZWF0b3I+CjxjYzpBZ2VudD4KPGRjOnRpdGxlPk1hdHBsb3RsaWIgdjMuOC4zLCBodHRwczovL21hdHBsb3RsaWIub3JnLzwvZGM6dGl0bGU+CjwvY2M6QWdlbnQ+CjwvZGM6Y3JlYXRvcj4KPC9jYzpXb3JrPgo8L3JkZjpSREY+CjwvbWV0YWRhdGE+CjxkZWZzPgo8c3R5bGUgdHlwZT0idGV4dC9jc3MiPip7c3Ryb2tlLWxpbmVqb2luOiByb3VuZDsgc3Ryb2tlLWxpbmVjYXA6IGJ1dHR9PC9zdHlsZT4KPC9kZWZzPgo8cGF0aCBkPSJtMCAzNDUuNmg0NjAuOHYtMzQ1LjZoLTQ2MC44eiIgZmlsbD0iI2ZmZiIvPgo8ZyBmaWxsPSJub25lIiBzdHJva2U9IiMwMDAiPgo8cGF0aCBkPSJtMjMwLjQgMjkuOTktNjMuNDcxIDcxLjQwNSIgY2xpcC1wYXRoPSJ1cmwoI2EpIi8+CjxwYXRoIGQ9Im0yMzAuNCAyOS45OSA2My40NzEgNzEuNDA1IiBjbGlwLXBhdGg9InVybCgjYSkiLz4KPHBhdGggZD0ibTE2Ni45MyAxMDEuNC0xMjYuOTQgNzEuNDA1IiBjbGlwLXBhdGg9InVybCgjYSkiLz4KPHBhdGggZD0ibTE2Ni45MyAxMDEuNHY3MS40MDUiIGNsaXAtcGF0aD0idXJsKCNhKSIvPgo8cGF0aCBkPSJtMjkzLjg3IDEwMS40djcxLjQwNSIgY2xpcC1wYXRoPSJ1cmwoI2EpIi8+CjxwYXRoIGQ9Im0yOTMuODcgMTAxLjQgMTI2Ljk0IDcxLjQwNSIgY2xpcC1wYXRoPSJ1cmwoI2EpIi8+CjxwYXRoIGQ9Im0xNjYuOTMgMTcyLjgtMTI2Ljk0IDcxLjQwNSIgY2xpcC1wYXRoPSJ1cmwoI2EpIi8+CjxwYXRoIGQ9Im0xNjYuOTMgMTcyLjh2NzEuNDA1IiBjbGlwLXBhdGg9InVybCgjYSkiLz4KPHBhdGggZD0ibTI5My44NyAxNzIuOHY3MS40MDUiIGNsaXAtcGF0aD0idXJsKCNhKSIvPgo8cGF0aCBkPSJtMjkzLjg3IDE3Mi44IDEyNi45NCA3MS40MDUiIGNsaXAtcGF0aD0idXJsKCNhKSIvPgo8cGF0aCBkPSJtMjkzLjg3IDI0NC4yLTYzLjQ3MSA3MS40MDUiIGNsaXAtcGF0aD0idXJsKCNhKSIvPgo8cGF0aCBkPSJtMjkzLjg3IDI0NC4yIDYzLjQ3MSA3MS40MDUiIGNsaXAtcGF0aD0idXJsKCNhKSIvPgo8L2c+CjxkZWZzPgo8cGF0aCBpZD0iYiIgZD0ibTAgMjcuMzg2YzcuMjYyOSAwIDE0LjIyOS0yLjg4NTYgMTkuMzY1LTguMDIxMnM4LjAyMTItMTIuMTAyIDguMDIxMi0xOS4zNjUtMi44ODU2LTE0LjIyOS04LjAyMTItMTkuMzY1LTEyLjEwMi04LjAyMTItMTkuMzY1LTguMDIxMi0xNC4yMjkgMi44ODU2LTE5LjM2NSA4LjAyMTItOC4wMjEyIDEyLjEwMi04LjAyMTIgMTkuMzY1IDIuODg1NiAxNC4yMjkgOC4wMjEyIDE5LjM2NSAxMi4xMDIgOC4wMjEyIDE5LjM2NSA4LjAyMTJ6IiBzdHJva2U9IiMwMDAiLz4KPC9kZWZzPgo8ZyBjbGlwLXBhdGg9InVybCgjYSkiIGZpbGw9IiNhZGQ4ZTYiIHN0cm9rZT0iIzAwMDAwMCI+Cjx1c2UgeD0iMjMwLjM5OTUxOSIgeT0iMjkuOTkwMDgzIiB4bGluazpocmVmPSIjYiIvPgo8dXNlIHg9IjE2Ni45MjgyODQiIHk9IjEwMS4zOTUwNDEiIHhsaW5rOmhyZWY9IiNiIi8+Cjx1c2UgeD0iMjkzLjg3MDc1NCIgeT0iMTAxLjM5NTA0MSIgeGxpbms6aHJlZj0iI2IiLz4KPHVzZSB4PSIzOS45ODY3NzciIHk9IjE3Mi44IiB4bGluazpocmVmPSIjYiIvPgo8dXNlIHg9IjE2Ni45MjgyODQiIHk9IjE3Mi44IiB4bGluazpocmVmPSIjYiIvPgo8dXNlIHg9IjM5Ljk4Njc3NyIgeT0iMjQ0LjIwNDk1OSIgeGxpbms6aHJlZj0iI2IiLz4KPHVzZSB4PSIxNjYuOTI4Mjg0IiB5PSIyNDQuMjA0OTU5IiB4bGluazpocmVmPSIjYiIvPgo8dXNlIHg9IjI5My44NzA3NTQiIHk9IjE3Mi44IiB4bGluazpocmVmPSIjYiIvPgo8dXNlIHg9IjQyMC44MTMyMjMiIHk9IjE3Mi44IiB4bGluazpocmVmPSIjYiIvPgo8dXNlIHg9IjI5My44NzA3NTQiIHk9IjI0NC4yMDQ5NTkiIHhsaW5rOmhyZWY9IiNiIi8+Cjx1c2UgeD0iNDIwLjgxMzIyMyIgeT0iMjQ0LjIwNDk1OSIgeGxpbms6aHJlZj0iI2IiLz4KPHVzZSB4PSIyMzAuMzk5NTE5IiB5PSIzMTUuNjA5OTE3IiB4bGluazpocmVmPSIjYiIvPgo8dXNlIHg9IjM1Ny4zNDE5ODgiIHk9IjMxNS42MDk5MTciIHhsaW5rOmhyZWY9IiNiIi8+CjwvZz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIj4KPGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoMjE1LjIzIDMyLjc0OSkgc2NhbGUoLjEgLS4xKSI+CjxkZWZzPgo8cGF0aCBpZD0iZCIgdHJhbnNmb3JtPSJzY2FsZSguMDE1NjI1KSIgZD0ibTU1MCA0ODYzaDE5NDF2LTcwNGgtODc4di00MzAwaDg3OHYtNzAzaC0xOTQxdjU3MDd6Ii8+CjxwYXRoIGlkPSJpIiB0cmFuc2Zvcm09InNjYWxlKC4wMTU2MjUpIiBkPSJtNzUwIDgzMWgxMDYzdjMwMTZsLTEwOTEtMjI1djgxOWwxMDg0IDIyNWgxMTQ0di0zODM1aDEwNjN2LTgzMWgtMzI2M3Y4MzF6Ii8+CjxwYXRoIGlkPSJlIiB0cmFuc2Zvcm09InNjYWxlKC4wMTU2MjUpIiBkPSJtNjUzIDEyMDloMTEyNXYtOTUzbC03NzItMTE2NWgtNjY1bDMxMiAxMTY1djk1M3oiLz4KPHBhdGggaWQ9ImciIHRyYW5zZm9ybT0ic2NhbGUoLjAxNTYyNSkiIGQ9Im00MjggNDY2NmgzNTE2di02NzhsLTE4MTktMzk4OGgtMTE3MmwxNzIyIDM3ODFoLTIyNDd2ODg1eiIvPgo8cGF0aCBpZD0iYyIgdHJhbnNmb3JtPSJzY2FsZSguMDE1NjI1KSIgZD0ibTIzNzUtODQ0aC0xOTQxdjcwM2g4Nzl2NDMwMGgtODc5djcwNGgxOTQxdi01NzA3eiIvPgo8L2RlZnM+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNpIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2ciLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIj4KPGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoMTUxLjc2IDEwNC4xNSkgc2NhbGUoLjEgLS4xKSI+CjxkZWZzPgo8cGF0aCBpZD0iaCIgdHJhbnNmb3JtPSJzY2FsZSguMDE1NjI1KSIgZD0ibTI5ODEgMjUxNnE0NzItMTIyIDcxNy00MjQgMjQ2LTMwMSAyNDYtNzY3IDAtNjk0LTUzMi0xMDU1LTUzMS0zNjEtMTU0OS0zNjEtMzYwIDAtNzIxIDU4dC03MTQgMTc0djkyOHEzMzgtMTY5IDY3MC0yNTUgMzMzLTg2IDY1NS04NiA0NzggMCA3MzMgMTY1IDI1NSAxNjYgMjU1IDQ3NiAwIDMxOS0yNjEgNDgzdC03NzEgMTY0aC00ODF2Nzc1aDUwNnE0NTQgMCA2NzUgMTQyIDIyMiAxNDIgMjIyIDQzMyAwIDI2OC0yMTYgNDE1LTIxNSAxNDctNjA5IDE0Ny0yOTAgMC01ODctNjYtMjk3LTY1LTU5MS0xOTN2ODgxcTM1NiAxMDAgNzA2IDE1MHQ2ODggNTBxOTA5IDAgMTM2MC0yOTkgNDUyLTI5OCA0NTItODk4IDAtNDA5LTIxNi02NzAtMjE1LTI2MS02MzctMzY3eiIvPgo8L2RlZnM+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNpIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2giLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIj4KPGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoMjQuODE5IDE3NS41Nikgc2NhbGUoLjEgLS4xKSI+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNpIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2kiLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIj4KPGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoMTUxLjc2IDE3NS41Nikgc2NhbGUoLjEgLS4xKSI+CjxkZWZzPgo8cGF0aCBpZD0ibCIgdHJhbnNmb3JtPSJzY2FsZSguMDE1NjI1KSIgZD0ibTE4NDQgODg0aDIwNTN2LTg4NGgtMzM5MXY4ODRsMTcwMyAxNTA0cTIyOSAyMDYgMzM4IDQwM3QxMDkgNDA5cTAgMzI4LTIyMCA1Mjh0LTU4NiAyMDBxLTI4MSAwLTYxNi0xMjAtMzM0LTEyMC03MTUtMzU4djEwMjVxNDA2IDEzNCA4MDMgMjA0IDM5NyA3MSA3NzggNzEgODM4IDAgMTMwMi0zNjkgNDY0LTM2OCA0NjQtMTAyOCAwLTM4MS0xOTctNzExLTE5Ny0zMjktODI4LTg4M2wtOTk3LTg3NXoiLz4KPC9kZWZzPgo8dXNlIHhsaW5rOmhyZWY9IiNkIi8+Cjx1c2UgeD0iNDUuNzAzMTI1IiB4bGluazpocmVmPSIjbCIvPgo8dXNlIHg9IjExNS4yODMyMDMiIHhsaW5rOmhyZWY9IiNlIi8+Cjx1c2UgeD0iMTUzLjI3MTQ4NCIgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0yMCIvPgo8dXNlIHg9IjE4OC4wODU5MzgiIHhsaW5rOmhyZWY9IiNoIi8+Cjx1c2UgeD0iMjU3LjY2NjAxNiIgeGxpbms6aHJlZj0iI2MiLz4KPC9nPgo8L2c+CjxnIGNsaXAtcGF0aD0idXJsKCNhKSI+CjxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDI0LjgxOSAyNDYuOTYpIHNjYWxlKC4xIC0uMSkiPgo8dXNlIHhsaW5rOmhyZWY9IiNkIi8+Cjx1c2UgeD0iNDUuNzAzMTI1IiB4bGluazpocmVmPSIjbCIvPgo8dXNlIHg9IjExNS4yODMyMDMiIHhsaW5rOmhyZWY9IiNlIi8+Cjx1c2UgeD0iMTUzLjI3MTQ4NCIgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0yMCIvPgo8dXNlIHg9IjE4OC4wODU5MzgiIHhsaW5rOmhyZWY9IiNsIi8+Cjx1c2UgeD0iMjU3LjY2NjAxNiIgeGxpbms6aHJlZj0iI2MiLz4KPC9nPgo8L2c+CjxnIGNsaXAtcGF0aD0idXJsKCNhKSI+CjxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDE1MS43NiAyNDYuOTYpIHNjYWxlKC4xIC0uMSkiPgo8dXNlIHhsaW5rOmhyZWY9IiNkIi8+Cjx1c2UgeD0iNDUuNzAzMTI1IiB4bGluazpocmVmPSIjaCIvPgo8dXNlIHg9IjExNS4yODMyMDMiIHhsaW5rOmhyZWY9IiNlIi8+Cjx1c2UgeD0iMTUzLjI3MTQ4NCIgeGxpbms6aHJlZj0iI0RlamFWdVNhbnMtQm9sZC0yMCIvPgo8dXNlIHg9IjE4OC4wODU5MzgiIHhsaW5rOmhyZWY9IiNoIi8+Cjx1c2UgeD0iMjU3LjY2NjAxNiIgeGxpbms6aHJlZj0iI2MiLz4KPC9nPgo8L2c+CjxnIGNsaXAtcGF0aD0idXJsKCNhKSI+CjxnIHRyYW5zZm9ybT0idHJhbnNsYXRlKDI3OC43IDEwNC4xNSkgc2NhbGUoLjEgLS4xKSI+CjxkZWZzPgo8cGF0aCBpZD0iZiIgdHJhbnNmb3JtPSJzY2FsZSguMDE1NjI1KSIgZD0ibTIzNTYgMzY3NS0xMzE4LTE5NTNoMTMxOHYxOTUzem0tMjAwIDk5MWgxMzM4di0yOTQ0aDY2NXYtODcyaC02NjV2LTg1MGgtMTEzOHY4NTBoLTIwNjh2MTAzMWwxODY4IDI3ODV6Ii8+CjwvZGVmcz4KPHVzZSB4bGluazpocmVmPSIjZCIvPgo8dXNlIHg9IjQ1LjcwMzEyNSIgeGxpbms6aHJlZj0iI2YiLz4KPHVzZSB4PSIxMTUuMjgzMjAzIiB4bGluazpocmVmPSIjZSIvPgo8dXNlIHg9IjE1My4yNzE0ODQiIHhsaW5rOmhyZWY9IiNEZWphVnVTYW5zLUJvbGQtMjAiLz4KPHVzZSB4PSIxODguMDg1OTM4IiB4bGluazpocmVmPSIjZyIvPgo8dXNlIHg9IjI1Ny42NjYwMTYiIHhsaW5rOmhyZWY9IiNjIi8+CjwvZz4KPC9nPgo8ZyBjbGlwLXBhdGg9InVybCgjYSkiPgo8ZyB0cmFuc2Zvcm09InRyYW5zbGF0ZSgyNzguNyAxNzUuNTYpIHNjYWxlKC4xIC0uMSkiPgo8ZGVmcz4KPHBhdGggaWQ9ImoiIHRyYW5zZm9ybT0ic2NhbGUoLjAxNTYyNSkiIGQ9Im0yMzE2IDIzMDNxLTMxNiAwLTQ3NC0yMDUtMTU4LTIwNC0xNTgtNjE0IDAtNDA5IDE1OC02MTQgMTU4LTIwNCA0NzQtMjA0IDMxOCAwIDQ3NiAyMDQgMTU4IDIwNSAxNTggNjE0IDAgNDEwLTE1OCA2MTQtMTU4IDIwNS00NzYgMjA1em0xNDg3IDIyNDF2LTg2M3EtMjk3IDE0MS01NjAgMjA4LTI2MiA2Ny01MTIgNjctNTM3IDAtODM3LTI5OS0zMDAtMjk4LTM1MC04ODUgMjA2IDE1MyA0NDYgMjI5IDI0MSA3NyA1MjYgNzcgNzE1IDAgMTE1NC00MTkgNDM5LTQxOCA0MzktMTA5NiAwLTc1MC00OTEtMTIwMi00OTAtNDUyLTEzMTUtNDUyLTkwOSAwLTE0MDggNjE0LTQ5OCA2MTUtNDk4IDE3NDMgMCAxMTU2IDU4MyAxODE3dDE1OTggNjYxcTMyMiAwIDYyNS01MHQ2MDAtMTUweiIvPgo8L2RlZnM+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNmIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2oiLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIj4KPGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoMjc4LjcgMjQ2Ljk2KSBzY2FsZSguMSAtLjEpIj4KPGRlZnM+CjxwYXRoIGlkPSJrIiB0cmFuc2Zvcm09InNjYWxlKC4wMTU2MjUpIiBkPSJtNjc4IDQ2NjZoMjk5MXYtODg1aC0yMDMxdi03MjJxMTM3IDM4IDI3NiA1OCAxMzkgMjEgMjg5IDIxIDg1MyAwIDEzMjgtNDI3dDQ3NS0xMTg5cTAtNzU2LTUxNy0xMTg1LTUxNy00MjgtMTQzNi00MjgtMzk3IDAtNzg2IDc3dC03NzMgMjMzdjk0N3EzODEtMjE5IDcyMy0zMjkgMzQyLTEwOSA2NDYtMTA5IDQzNyAwIDY4OCAyMTQgMjUyIDIxNCAyNTIgNTgwIDAgMzY5LTI1MiA1ODEtMjUxIDIxMy02ODggMjEzLTI2MCAwLTU1NC02OC0yOTMtNjctNjMxLTIwN3YyNjI1eiIvPgo8L2RlZnM+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNmIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2siLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIj4KPGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoMjE1LjIzIDMxOC4zNykgc2NhbGUoLjEgLS4xKSI+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNmIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2YiLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIj4KPGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoMzQyLjE3IDMxOC4zNykgc2NhbGUoLjEgLS4xKSI+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNrIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2siLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIj4KPGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoNDA1LjY1IDI0Ni45Nikgc2NhbGUoLjEgLS4xKSI+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNqIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2oiLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGcgY2xpcC1wYXRoPSJ1cmwoI2EpIj4KPGcgdHJhbnNmb3JtPSJ0cmFuc2xhdGUoNDA1LjY1IDE3NS41Nikgc2NhbGUoLjEgLS4xKSI+Cjx1c2UgeGxpbms6aHJlZj0iI2QiLz4KPHVzZSB4PSI0NS43MDMxMjUiIHhsaW5rOmhyZWY9IiNnIi8+Cjx1c2UgeD0iMTE1LjI4MzIwMyIgeGxpbms6aHJlZj0iI2UiLz4KPHVzZSB4PSIxNTMuMjcxNDg0IiB4bGluazpocmVmPSIjRGVqYVZ1U2Fucy1Cb2xkLTIwIi8+Cjx1c2UgeD0iMTg4LjA4NTkzOCIgeGxpbms6aHJlZj0iI2ciLz4KPHVzZSB4PSIyNTcuNjY2MDE2IiB4bGluazpocmVmPSIjYyIvPgo8L2c+CjwvZz4KPGRlZnM+CjxjbGlwUGF0aCBpZD0iYSI+CjxyZWN0IHdpZHRoPSI0NjAuOCIgaGVpZ2h0PSIzNDUuNiIvPgo8L2NsaXBQYXRoPgo8L2RlZnM+Cjwvc3ZnPgo=)

Matcom Online Grader Faculty of Mathematics and Computer Science of University of Havana

The 2024 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

K - Keen Tree Design

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

Input

Output

Sample test(s)

Hints

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana