h2. Restricţii

* $1 ≤ N ≤ 70.000$
* $1 ≤ K ≤ 70.000$
* $1 ≤ z ≤ 1.000.000.000$
* Pentru $7$ puncte, $N ≤ 1.000$ şi $z ≤ 1.000$.
* Pentru alte $22$ puncte, Tanaka a găsit doar maxime.
* Pentru alte $29$ puncte, oricare două lanţuri pentru care Tanaka a găsit maxime nu se intersectează. De asemenea, oricare două lanţuri pentru care Tanaka a găsit minime nu se intersectează.

* 1 ≤ N ≤70.000
* 1 ≤ K ≤70.000
* 1 ≤ z ≤ 1.000.000.000
* Pentru 7 puncte, N ≤ 1.000 şi z ≤ 1.000.
* Pentru alte 22 puncte, Tanaka a găsit doar maxime.
* Pentru alte 29 puncte, oricare două lanţuri pentru care Tanaka a găsit maxime nu se intersectează. De asemenea, oricare două lanţuri pentru care Tanaka a găsit minime nu se intersectează.

h2. Exemple

table(example). |_. minmaxtree.in |_. minmaxtree.out |
| 4
1 2

M 1 2 1
m 1 4 0
M 2 3 100

|3 2 100

| 3 2 100

1 2 1
4 3 0
|

== include(page="template/taskfooter" task_id="minmaxtree") ==