/**
 * Fast IO and other utilities for C++ by EPICI
 */

#include <iostream>
#include <cstdint>

using namespace std;

// Rust-like sized integer names
typedef uint8_t u8;
typedef int8_t i8;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint32_t u32;
typedef int32_t i32;
typedef uint64_t u64;
typedef int64_t i64;
typedef float f32;
typedef double f64;
// the famous ll
typedef long long ll;
// 1e9 aka 10^9
const ll p10_9 = 1000000000;
// FAST READ/WRITE CHAR
#define gc() getchar_unlocked()
#define pc(x) putchar_unlocked(x)
// FAST READ INT/UINT
#define readuint(x) _=gc();while(_<=32){_=gc();}tmp=0;while(_>32){tmp=(tmp<<3)+(tmp<<1)+_-48;_=gc();}x=tmp;
#define readint(x) _=gc();while(_<=32){_=gc();}tr=1;if(_==45){tr=-1;_=gc();}tmp=0;while(_>32){tmp=(tmp<<3)+(tmp<<1)+_-48;_=gc();}x=tmp*tr;
// FAST WRITE INT/UINT
#define writeuintseg(a,b,c) while(tmp>=c){td=(tmp*a)>>b;tr=tmp-(td<<3)-(td<<1);buf[++pt]=tr+48;tmp=td;}
// breaks at exactly 0x40000005 = 1073741829 > 1e9
#define writeuintpad(x,y) pt=-1;tmp=x; \
writeuintseg(0xccccccd,31,0x4000005); \
writeuintseg(0xcccccd,27,0x400005); \
writeuintseg(0xccccd,23,0x40005); \
writeuintseg(0xcccd,19,1); \
for(;pt<(y-1);){buf[++pt]=48;} \
for(;pt>=0;pt--){pc(buf[pt]);}
#define writeuintnz(x) writeuintpad(x,0);
#define writeuint(x) writeuintpad(x,1);
#define writeint(x) tmp=x;if(tmp<0){pc(45);tmp=-tmp;}writeuint(tmp);
// breaks at exactly 0x40000005 * 1e9 = 1073741829000000000 > 1e18
#define writeluintnz(x) tmp2=x;if(tmp2<p10_9){ \
writeuintnz(tmp2);}else{tdt=lldiv(tmp2,p10_9); \
writeuintnz(tdt.quot); \
writeuintpad(tdt.rem,9);}
#define writeluint(x) tmp2=x;if(tmp2<p10_9){writeuintnz(tmp2);}else{ \
tdt=lldiv(tmp2,p10_9); \
writeuintnz(tdt.quot); \
writeuintpad(tdt.rem,9);}
#define writelint(x) tmp2=x;if(tmp2<0){pc(45);tmp2=-tmp2;}writeluint(tmp2);
// used by fast IO
char buf[10];
int pt;
ll tmp,tmp2,td,tr;
lldiv_t tdt;
char _;
// good hash combiner, stolen from boost
const size_t magic_p = 0x9e3779b9;
const size_t hash_combine(const size_t& first, const size_t& second) {
    auto x = first * magic_p + second;
    return (x >> 19) ^ x;
}
// use this for hash on pair to allow using pair in unordered containers
struct pair_hash {
    template <typename T1, typename T2> const size_t operator () (const pair<T1,T2>& value) {
        auto h1 = hash<T1>()(value.first);
        auto h2 = hash<T2>()(value.second);
        return hash_combine(h1, h2);
    }
};
//unordered_set<pair<ll,ll>, pair_hash> example;