#define easter_egg M;
#define luigi &i:
#define piccionebuco pq;
#define catalan 1e18;
#define camice u
#define timmy_loves_gambling namespace
#define BASTAAAA 0;
#define topolino d,
#define we N;
#define piccionemagico mincammino
#define nonsocosastofacendo &
#define qwertyuiopasdfghjklzxcvbnm :
#define IPERSUSSONE M
#define aria for
#define sunnov8238pm .push_back
#define chescemochesonoio int,
#define CIAISSIMO 1;
#define quaqua G
#define bfs std;
#define fragola cin
#define HOPERSO long
#define qualcunomistaguardando main
#define super_perdita u,
#define biscottiniii Y
#define seisette w
#define hehehe N,
#define AFS_PROBLEMA_SEGRETO priority_queue
#define ohnoooo ,
#define gnamgnam i
#define sus 1e17
#define mario N
#define iorewivfj w;
#define toad auto
#define pkhoviintoleoiimadaicirendiamocontodovesiamofinitiHAHAHAHA d
#define scioccherellinooo 0
#define papera 0,
#define piccionebasta pq.top
#define tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema int
#define scotch void
#define camicie X
#define googleChrome pq.pop
#define POV_DEI_BISCOTTI D
#define timmy_likes_dp v
#define paperago P,
#define pikapikaCHUUUUUUCHUHCUSIDVJAO Y,
#define sixseven pq.emplace
#define z pair
#define tungtungsteno X,
#define ifohncm P
#define blublurblablubbluss M,
#define blurb while
#define tastiera ;
#define ciao long,
#define susssone vector
#define settantatrequarantadue using
#define sussizerello !pq.empty
#define cfs if
#include <bits/stdc++.h>
settantatrequarantadue timmy_loves_gambling bfs 
 
#define ll long long
#include <cassert>
 
scotch piccionemagico(tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema hehehe tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema blublurblablubbluss susssone<tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema> tungtungsteno susssone<tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema> pikapikaCHUUUUUUCHUHCUSIDVJAO susssone<tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema> paperago susssone<HOPERSO HOPERSO>nonsocosastofacendo POV_DEI_BISCOTTI) { 
    AFS_PROBLEMA_SEGRETO<z<HOPERSO ciao HOPERSO HOPERSO>> piccionebuco 
 
    susssone < susssone < z<chescemochesonoio tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema> > > quaqua ( mario )tastiera 
 
    aria(tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema gnamgnam = BASTAAAA gnamgnam < we gnamgnam ++) { 
        POV_DEI_BISCOTTI[gnamgnam] = catalan 
    } 
 
    POV_DEI_BISCOTTI[scioccherellinooo] = BASTAAAA 
 
    aria(tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema gnamgnam = BASTAAAA gnamgnam < easter_egg gnamgnam++) { 
        quaqua[camicie[gnamgnam]]sunnov8238pm({biscottiniii[gnamgnam]ohnoooo ifohncm[gnamgnam]})tastiera 
    } 
 
    sixseven(papera scioccherellinooo)tastiera 
 
    blurb(sussizerello()) { 
        toad [topolino timmy_likes_dp] = piccionebasta()tastiera 
        googleChrome()tastiera 
 
        aria(toad [super_perdita seisette]qwertyuiopasdfghjklzxcvbnm quaqua[timmy_likes_dp]) { 
            cfs(POV_DEI_BISCOTTI[camice] > -pkhoviintoleoiimadaicirendiamocontodovesiamofinitiHAHAHAHA + seisette) { 
                POV_DEI_BISCOTTI[camice] = - pkhoviintoleoiimadaicirendiamocontodovesiamofinitiHAHAHAHA + iorewivfj 
                sixseven(-POV_DEI_BISCOTTI[camice]ohnoooo camice)tastiera 
            } 
        } 
    } 
 
    aria(toad luigi POV_DEI_BISCOTTI) cfs(gnamgnam >= sus) gnamgnam = -CIAISSIMO 
} 
 
 
#ifndef EVAL
tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema qualcunomistaguardando() { 
    tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema hehehe easter_egg 
    fragola >> mario >> easter_egg 
 
    susssone<tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema> camicie(IPERSUSSONE)ohnoooo biscottiniii(IPERSUSSONE)ohnoooo ifohncm(IPERSUSSONE)tastiera 
    susssone<HOPERSO HOPERSO> POV_DEI_BISCOTTI(mario)tastiera 
 
    aria (tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema gnamgnam = BASTAAAA gnamgnam < easter_egg gnamgnam++) { 
        fragola >> camicie[gnamgnam] >> biscottiniii[gnamgnam] >> ifohncm[gnamgnam]tastiera 
    } 
 
    piccionemagico(hehehe blublurblablubbluss tungtungsteno pikapikaCHUUUUUUCHUHCUSIDVJAO paperago POV_DEI_BISCOTTI)tastiera 
 
 
} 
#endif