#include <bits/stdc++.h> #define nmax 100005 #define imax 17 #define reset(x) memset(x, 0, sizeof(x)) #define data datafuckyoubach #define apcDEGaS using #define NIQYTNBZ namespace #define SqWHEsZe std #define ophxPdev typedef #define KfkSEnhm long #define AyKBOLdX lli #define tWmSlaHd pair #define RQOwZXYM pii #define cxjdsJqE vector #define qfZjiXyG a #define TbpaNxaX nmax #define kXckJsdz n #define IaEvReAs k #define YsNfrGoX x #define nOeMycyN y #define NmpXEcDY d #define hGXzyZOA cha #define WeUKLKPH f #define vzRrYXaQ bool #define yYNDcWtS avail #define UHFpEwjm s #define couPvbfA imax #define oMKTbtif void #define xHEDPtCm DFS #define BcfJoVuy u #define ySkTJExl true #define OYeXyAsP for #define hjXZHdom auto #define vCvUitWC v #define uDkkVqzG if #define NygKRGkh first #define ahgbHCWP second #define VbdIJFPB buildtable #define kJnNxLmU memset #define ByiIMiJo sizeof #define NvTBhTEe i #define zcCDvqao j #define ZQQsPSGY query #define ZRzewcJj swap #define TVXnkhyU log #define oSJYniSv log2 #define ejlPPNQF return #define UJHbdITZ int #define ovUHyhcV main #define KtLHCAjV ios #define mGnLobws sync_with_stdio #define dLDjfjPM cin #define uYFADJiP tie #define NXmRrkVj cout #define vaJkapYk while #define Iiviiprm exit #define EyncZOzG push_back #define ynnpvVgH nhapxuat #define eiCYDmoH hj #define PDMHSSxl chjj #define XxBxPbIs reset #define SJICrCqM clear #define ENDCODE ; #define NNO { #define NNC } #define DIVSET /= #define ADDSET += #define SUBSET -= #define MULSET *= #define DIFSET != #define MODSET %= #define XORSET ^= #define ORXSET |= #define ANDXSET &= #define OR || #define AND && #define DOT . #define PAY , #define CCO ( #define CCC ) #define MUL * #define DIV / #define SUBSUB -- #define ADDADD ++ #define ADD + #define SUB - #define MOD % #define XOR ^ #define WTF ? #define ANDX & #define ORX | #define EQUL == #define IN >> #define OUT << #define LOWSET <= #define HIGHSET >= #define CTRO -> #define DIF ! #define SET = #define LOW < #define HIGH > apcDEGaS NIQYTNBZ SqWHEsZe ENDCODE ophxPdev KfkSEnhm KfkSEnhm AyKBOLdX ENDCODE ophxPdev tWmSlaHd LOW AyKBOLdX, AyKBOLdX HIGH RQOwZXYM ENDCODE cxjdsJqE LOW RQOwZXYM HIGH qfZjiXyG[TbpaNxaX] ENDCODE AyKBOLdX kXckJsdz, IaEvReAs, YsNfrGoX, nOeMycyN, NmpXEcDY[TbpaNxaX], hGXzyZOA[TbpaNxaX], WeUKLKPH[TbpaNxaX] ENDCODE vzRrYXaQ yYNDcWtS[TbpaNxaX] ENDCODE AyKBOLdX UHFpEwjm[couPvbfA][TbpaNxaX] ENDCODE oMKTbtif xHEDPtCm(AyKBOLdX BcfJoVuy) NNO yYNDcWtS[BcfJoVuy] SET ySkTJExl ENDCODE OYeXyAsP(hjXZHdom vCvUitWC : qfZjiXyG[BcfJoVuy]) NNO uDkkVqzG(DIF yYNDcWtS[vCvUitWC.NygKRGkh]) NNO NmpXEcDY[vCvUitWC.NygKRGkh] SET NmpXEcDY[BcfJoVuy] ADD 1 ENDCODE WeUKLKPH[vCvUitWC.NygKRGkh] SET WeUKLKPH[BcfJoVuy] ADD vCvUitWC .ahgbHCWP ENDCODE hGXzyZOA[vCvUitWC.NygKRGkh] SET BcfJoVuy ENDCODE xHEDPtCm(vCvUitWC.NygKRGkh) ENDCODE NNC NNC NNC oMKTbtif VbdIJFPB() NNO kJnNxLmU(UHFpEwjm, SUB 1, ByiIMiJo UHFpEwjm) ENDCODE OYeXyAsP(AyKBOLdX NvTBhTEe SET 0 ENDCODE NvTBhTEe LOWSET kXckJsdz SUB 1 ENDCODE NvTBhTEe ADDADD) UHFpEwjm[0][NvTBhTEe] SET hGXzyZOA[NvTBhTEe] ENDCODE OYeXyAsP(AyKBOLdX NvTBhTEe SET 1 ENDCODE(1 OUT NvTBhTEe) LOWSET kXckJsdz ENDCODE NvTBhTEe ADDADD) NNO OYeXyAsP(AyKBOLdX zcCDvqao SET 0 ENDCODE zcCDvqao LOWSET kXckJsdz SUB 1 ENDCODE zcCDvqao ADDADD) NNO uDkkVqzG(UHFpEwjm[NvTBhTEe SUB 1][zcCDvqao] DIFSET SUB 1) UHFpEwjm[NvTBhTEe][zcCDvqao] SET UHFpEwjm[NvTBhTEe SUB 1][UHFpEwjm[NvTBhTEe SUB 1][zcCDvqao]] ENDCODE NNC NNC NNC AyKBOLdX ZQQsPSGY(AyKBOLdX BcfJoVuy, AyKBOLdX vCvUitWC) NNO uDkkVqzG(NmpXEcDY[BcfJoVuy] LOW NmpXEcDY[vCvUitWC]) ZRzewcJj(BcfJoVuy, vCvUitWC) ENDCODE AyKBOLdX TVXnkhyU SET oSJYniSv(NmpXEcDY[BcfJoVuy]) ENDCODE OYeXyAsP(AyKBOLdX NvTBhTEe SET TVXnkhyU ENDCODE NvTBhTEe HIGHSET 0 ENDCODE NvTBhTEe SUBSUB) NNO uDkkVqzG(NmpXEcDY[BcfJoVuy] SUB(1 OUT NvTBhTEe) HIGHSET NmpXEcDY[vCvUitWC]) BcfJoVuy SET UHFpEwjm[NvTBhTEe][BcfJoVuy] ENDCODE NNC uDkkVqzG(BcfJoVuy EQUL vCvUitWC) ejlPPNQF BcfJoVuy ENDCODE OYeXyAsP(AyKBOLdX NvTBhTEe SET TVXnkhyU ENDCODE NvTBhTEe HIGHSET 0 ENDCODE NvTBhTEe SUBSUB) NNO uDkkVqzG(UHFpEwjm[NvTBhTEe][BcfJoVuy] DIFSET SUB 1 AND UHFpEwjm[NvTBhTEe][BcfJoVuy] DIFSET UHFpEwjm[NvTBhTEe][vCvUitWC]) NNO BcfJoVuy SET UHFpEwjm[NvTBhTEe][BcfJoVuy] ENDCODE vCvUitWC SET UHFpEwjm[NvTBhTEe][vCvUitWC] ENDCODE NNC NNC ejlPPNQF hGXzyZOA[BcfJoVuy] ENDCODE NNC UJHbdITZ ovUHyhcV() NNO KtLHCAjV::mGnLobws(0) ENDCODE dLDjfjPM.uYFADJiP(0) ENDCODE NXmRrkVj .uYFADJiP(0) ENDCODE vaJkapYk(1) NNO dLDjfjPM IN kXckJsdz ENDCODE uDkkVqzG(kXckJsdz EQUL 0) Iiviiprm(0) ENDCODE OYeXyAsP(AyKBOLdX BcfJoVuy, vCvUitWC, NvTBhTEe SET 1 ENDCODE NvTBhTEe LOW kXckJsdz ENDCODE NvTBhTEe ADDADD) NNO dLDjfjPM IN BcfJoVuy IN vCvUitWC ENDCODE qfZjiXyG[BcfJoVuy] .EyncZOzG(NNO NvTBhTEe, vCvUitWC NNC) ENDCODE qfZjiXyG[NvTBhTEe] .EyncZOzG(NNO BcfJoVuy, vCvUitWC NNC) ENDCODE NNC hGXzyZOA[0] SET SUB 1 ENDCODE NmpXEcDY[0] SET 0 ENDCODE xHEDPtCm(0) ENDCODE VbdIJFPB() ENDCODE UJHbdITZ ynnpvVgH ENDCODE dLDjfjPM IN ynnpvVgH ENDCODE vaJkapYk(ynnpvVgH SUBSUB) NNO dLDjfjPM IN YsNfrGoX IN nOeMycyN ENDCODE AyKBOLdX eiCYDmoH SET 0 ENDCODE UJHbdITZ PDMHSSxl SET ZQQsPSGY(YsNfrGoX, nOeMycyN) ENDCODE eiCYDmoH SET WeUKLKPH[YsNfrGoX] ADD WeUKLKPH[nOeMycyN] SUB WeUKLKPH[PDMHSSxl] MUL 2 ENDCODE NXmRrkVj OUT eiCYDmoH OUT " " ENDCODE NNC NXmRrkVj OUT "\n" ENDCODE XxBxPbIs(yYNDcWtS) ENDCODE XxBxPbIs(NmpXEcDY) ENDCODE XxBxPbIs(hGXzyZOA) ENDCODE XxBxPbIs(WeUKLKPH) ENDCODE OYeXyAsP(AyKBOLdX NvTBhTEe SET 0 ENDCODE NvTBhTEe LOW kXckJsdz ENDCODE NvTBhTEe ADDADD) qfZjiXyG[NvTBhTEe] .SJICrCqM() ENDCODE NNC ejlPPNQF 0 ENDCODE NNC