#line 1 "Main.cpp" #include #include #line 2 "nachia\\misc\\fastio.hpp" #include #include #include #line 6 "nachia\\misc\\fastio.hpp" namespace nachia{ struct CInStream{ private: static const unsigned int INPUT_BUF_SIZE = 1 << 17; unsigned int p = INPUT_BUF_SIZE; static char Q[INPUT_BUF_SIZE]; public: using MyType = CInStream; char seekChar() noexcept { if(p == INPUT_BUF_SIZE){ size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin); if(len != INPUT_BUF_SIZE) Q[len] = '\0'; p = 0; } return Q[p]; } void skipSpace() noexcept { while(isspace(seekChar())) p++; } uint32_t nextU32() noexcept { skipSpace(); uint32_t buf = 0; while(true){ char tmp = seekChar(); if('9' < tmp || tmp < '0') break; buf = buf * 10 + (tmp - '0'); p++; } return buf; } int32_t nextI32() noexcept { skipSpace(); if(seekChar() == '-'){ p++; return (int32_t)(-nextU32()); } return (int32_t)nextU32(); } uint64_t nextU64() noexcept { skipSpace(); uint64_t buf = 0; while(true){ char tmp = seekChar(); if('9' < tmp || tmp < '0') break; buf = buf * 10 + (tmp - '0'); p++; } return buf; } int64_t nextI64() noexcept { skipSpace(); if(seekChar() == '-'){ p++; return (int64_t)(-nextU64()); } return (int64_t)nextU64(); } char nextChar() noexcept { skipSpace(); char buf = seekChar(); p++; return buf; } std::string nextToken(){ skipSpace(); std::string buf; while(true){ char ch = seekChar(); if(isspace(ch) || ch == '\0') break; buf.push_back(ch); p++; } return buf; } MyType& operator>>(unsigned int& dest) noexcept { dest = nextU32(); return *this; } MyType& operator>>(int& dest) noexcept { dest = nextI32(); return *this; } MyType& operator>>(unsigned long& dest) noexcept { dest = nextU64(); return *this; } MyType& operator>>(long& dest) noexcept { dest = nextI64(); return *this; } MyType& operator>>(unsigned long long& dest) noexcept { dest = nextU64(); return *this; } MyType& operator>>(long long& dest) noexcept { dest = nextI64(); return *this; } MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; } MyType& operator>>(char& dest) noexcept { dest = nextChar(); return *this; } } cin; struct FastOutputTable{ char LZ[1000][4] = {}; char NLZ[1000][4] = {}; constexpr FastOutputTable(){ using u32 = uint_fast32_t; for(u32 d=0; d<1000; d++){ LZ[d][0] = ('0' + d / 100 % 10); LZ[d][1] = ('0' + d / 10 % 10); LZ[d][2] = ('0' + d / 1 % 10); LZ[d][3] = '\0'; } for(u32 d=0; d<1000; d++){ u32 i = 0; if(d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10); if(d >= 10) NLZ[d][i++] = ('0' + d / 10 % 10); if(d >= 1) NLZ[d][i++] = ('0' + d / 1 % 10); NLZ[d][i++] = '\0'; } } }; struct COutStream{ private: using u32 = uint32_t; using u64 = uint64_t; using MyType = COutStream; static const u32 OUTPUT_BUF_SIZE = 1 << 17; static char Q[OUTPUT_BUF_SIZE]; static constexpr FastOutputTable TB = FastOutputTable(); u32 p = 0; static constexpr u32 P10(u32 d){ return d ? P10(d-1)*10 : 1; } static constexpr u64 P10L(u32 d){ return d ? P10L(d-1)*10 : 1; } template static void Fil(T& m, U& l, U x) noexcept { m = l/x; l -= m*x; } void next_dig9(u32 x){ u32 y; Fil(y, x, P10(6)); nextCstr(TB.LZ[y]); Fil(y, x, P10(3)); nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]); } public: void nextChar(char c){ Q[p++] = c; if(p == OUTPUT_BUF_SIZE){ fwrite(Q, p, 1, stdout); p = 0; } } void nextEoln(){ nextChar('\n'); } void nextCstr(const char* s){ while(*s) nextChar(*(s++)); } void nextU32(uint32_t x){ u32 y = 0; if(x >= P10(9)){ Fil(y, x, P10(9)); nextCstr(TB.NLZ[y]); next_dig9(x); } else if(x >= P10(6)){ Fil(y, x, P10(6)); nextCstr(TB.NLZ[y]); Fil(y, x, P10(3)); nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]); } else if(x >= P10(3)){ Fil(y, x, P10(3)); nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]); } else if(x >= 1) nextCstr(TB.NLZ[x]); else nextChar('0'); } void nextI32(int32_t x){ if(x >= 0) nextU32(x); else{ nextChar('-'); nextU32((u32)-x); } } void nextU64(uint64_t x){ u32 y = 0; if(x >= P10L(18)){ Fil(y, x, P10L(18)); nextU32(y); Fil(y, x, P10L(9)); next_dig9(y); next_dig9(x); } else if(x >= P10L(9)){ Fil(y, x, P10L(9)); nextU32(y); next_dig9(x); } else nextU32(x); } void nextI64(int64_t x){ if(x >= 0) nextU64(x); else{ nextChar('-'); nextU64((u64)-x); } } void writeToFile(bool flush = false){ fwrite(Q, p, 1, stdout); if(flush) fflush(stdout); p = 0; } COutStream(){ Q[0] = 0; } ~COutStream(){ writeToFile(); } MyType& operator<<(unsigned int tg){ nextU32(tg); return *this; } MyType& operator<<(unsigned long tg){ nextU64(tg); return *this; } MyType& operator<<(unsigned long long tg){ nextU64(tg); return *this; } MyType& operator<<(int tg){ nextI32(tg); return *this; } MyType& operator<<(long tg){ nextI64(tg); return *this; } MyType& operator<<(long long tg){ nextI64(tg); return *this; } MyType& operator<<(const std::string& tg){ nextCstr(tg.c_str()); return *this; } MyType& operator<<(const char* tg){ nextCstr(tg); return *this; } MyType& operator<<(char tg){ nextChar(tg); return *this; } } cout; char CInStream::Q[INPUT_BUF_SIZE]; char COutStream::Q[OUTPUT_BUF_SIZE]; } // namespace nachia #line 4 "Main.cpp" using namespace std; #define rep(i,n) for(int i=0; i<(int)(n); i++) int main(){ using nachia::cin; using nachia::cout; int N; cin >> N; if(N == 1){ cout << "-1\n"; return 0; } vector Q((1<