#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#if __cplusplus >= 201103L
#include <array>
#include <random>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#else
#ifdef __GNUC__
#include <tr1/unordered_map>
#include <tr1/unordered_set>
using namespace tr1;
#else
#ifdef _MSC_VER
#include <hash_map>
#include <hash_set>
using namespace stdext;
#define unordered_map hash_map
#define unordered_set hash_set
#else
#include <unordered_map>
#include <unordered_set>
#endif
#endif
#endif

#define    FOR(i,a,n)       for(register int i=(a),_=(n)+1;i<_;++i)
#define    FIR(i,n,a)       for(register int i=(n),_=(a)-1;i>_;--i)
#define    FO(i,n)          for(register int i=0,_=(n);i<_;++i)
#define    FI(i,n)          for(register int i=(n)-1;i>=0;--i)
#define    all(a)           (a).begin(),(a).end()
#define    vlb(a,n)         (lower_bound(all(a),n)-(a).begin())
#define    vub(a,n)         (upper_bound(all(a),n)-(a).begin())
#define    vlbx(a,n)        ((a)[(lower_bound(all(a),n)-(a).begin())])
#define    vubx(a,n)        ((a)[(upper_bound(all(a),n)-(a).begin())])
#define    reunique(a)      (sort(all(a)), (a).resize(distance((a).begin(), unique(all(a)))))
#define    mem(a,b)         memset((a),(b),sizeof(a))
#define    sz(x)            (int((x).size()))
#define    lowbit(x)        ((x)&-(x))
#define    lch              p<<1,l,mid
#define    rch              p<<1|1,mid+1,r
#define    ll               (p<<1)
#define    rr               (p<<1|1)
#define    queues           priority_queue
#define    pb(a)            push_back(a)
#define    mp(a,b)          make_pair((a),(b))
#define    mt(a,b,c)        make_triple((a),(b),(c))
#define    lb               lower_bound
#define    ub               upper_bound
#define    ff               first
#define    ss               second
#define    tt               third
//#pragma    comment(linker, "/STACK:1024000000,1024000000")
//__attribute__((optimize("-O2")))
typedef    long long            LL;
typedef    unsigned long long   ULL;
typedef    double               db;
typedef    long double          ld;
typedef    pair<int,int>        PII;
typedef    pair<LL,LL>          PLL;
typedef    vector<bool>         VB;
typedef    vector<string>       VS;
typedef    vector<int>          VI;
typedef    vector<LL>           VL;
typedef    vector<PII>          VII;
typedef    vector<PLL>          VLL;
template<class T, class U, class O>struct triple { T first; U second; O third; triple() : first(T()), second(U()), third(O()) {} triple(const T& _a, const U& _b, const O& _c) :  first(_a), second(_b), third(_c) {} };
template<class T, class U, class O>bool operator < (const triple<T, U, O>&t1, const triple<T, U, O>&t2) { if(t1.first != t2.first) return t1.first < t2.first; else if(t1.second != t2.second) return t1.second < t2.second; else return t1.third < t2.trird; }
template<class T, class U, class O>bool operator > (const triple<T, U, O>&t1, const triple<T, U, O>&t2) { if(t1.first != t2.first) return t1.first > t2.first; else if(t1.second != t2.second) return t1.second > t2.second; else return t1.third > t2.trird; }
// Fast max and min *******************************************************************************
#define max(...) _max(__VA_ARGS__)
#define min(...) _min(__VA_ARGS__)
template<class T>inline T _max(T a, T b) { return a > b ? a : b; }
template<class T>inline T _min(T a, T b) { return a < b ? a : b; }
template<class T>inline T _max(T a, T b, T c) { return _max(a, _max(b, c)); }
template<class T>inline T _min(T a, T b, T c) { return _min(a, _min(b, c)); }
template<class T>inline T _max(T a, T b, T c, T d) { return _max(a, _max(b, c, d)); }
template<class T>inline T _min(T a, T b, T c, T d) { return _min(a, _min(b, c, d)); }
// Fast I/O ***************************************************************************************
#define Buff 100000
static char chr, _s[256], *be = _s, *en = _s + 255;
inline char gtc() { static char bfi[Buff], *ci = bfi - 1, *cl = ci; return ci == cl && (cl = (ci = bfi - 1) + fread(bfi, 1, Buff, stdin), ci == cl) ? 0 : *++ci; }
void readbit(double &ret, char ch = gtc()) { if(isdigit(ch)) readbit(ret), ret += ch ^ '0', ret *= 0.1; }
inline bool _read(int &res, char flag = '\0') { while(chr = gtc(), !isdigit(chr)) if(flag |= chr == '-', !chr) return false; for(res = 0; isdigit(chr); res += res << 2, res <<= 1, res += chr ^ '0', chr = gtc()); flag && (res = -res); return true; }
inline bool _read(unsigned int &res) { while(chr = gtc(), !isdigit(chr)) if(!chr) return false; for(res = 0; isdigit(chr); res += res << 2, res <<= 1, res += chr ^ '0', chr = gtc()); return true; }
inline bool _read(long long &res, char flag = '\0') { while(chr = gtc(), !isdigit(chr)) if(flag |= chr == '-', !chr) return false; for(res = 0; isdigit(chr); res += res << 2, res <<= 1, res += chr ^ '0', chr = gtc()); flag && (res = -res); return true; }
inline bool _read(unsigned long long &res) { while(chr = gtc(), !isdigit(chr)) if(!chr) return false; for(res = 0; isdigit(chr); res += res << 2, res <<= 1, res += chr ^ '0', chr = gtc()); return true; }
inline bool _read(double &ret, char flag = '\0', long long sum = 0) { while(chr = gtc(), !isdigit(chr)) if(flag |= chr == '-', !chr) return false; while(isdigit(chr)) sum += sum << 2, sum <<= 1, sum += chr ^ '0', chr = gtc(); if(ret = 0, chr == '.') readbit(ret), ret += 1e-9; ret += sum, flag && (ret = -ret); return true; }
inline bool _read(char *p) { while(chr = gtc(), (chr == ' ') || (chr == '\n') || (!chr)) if(!chr) return 0; while(chr ^ '\n' && chr ^ ' ' && chr) *p++ = chr, chr = gtc(); *p = 0; return 1; }
inline bool _read(string &s) { s.reserve(256), s.clear(); while(chr = gtc(), (chr == ' ') || (chr == '\n') || (!chr)) if(!chr) return 0; *en = 0; while(chr ^ '\n' && chr ^ ' ' && chr) *be++ = chr, be < en ? chr = gtc() : (be = _s, s.append(_s, en), chr = gtc()); *be = 0, s.append(_s, be), be = _s; return 1; }
inline bool gts(char *p) { while(chr = gtc(), (!chr)) if(!chr) return 0; while(chr ^ '\n' && chr) *p++ = chr, chr = gtc(); *p = 0; return 1; }
inline bool gts(string &s) { s.reserve(256), s.clear(); while(chr = gtc(), (!chr)) if(!chr) return 0; *en = 0; while(chr ^ '\n' && chr) *be++ = chr, be < en ? chr = gtc() : (be = _s, s.append(_s, en), chr = gtc()); *be = 0, s.append(_s, be), be = _s; return 1; }
template<class T, class U>inline bool _read(pair<T, U> &res) { return _read(res.ff), _read(res.ss); }
template<class T, class U, class O>inline bool _read(triple<T, U, O> &res) { return _read(res.ff), _read(res.ss), _read(res.tt); }
inline void ptc(char ch = 0) { static char bfo[Buff], *co = bfo - 1, *coe = co + Buff; !ch || (*++co=ch, co==coe) ? fwrite(bfo, 1, co-bfo+1, stdout), co = bfo - 1 : 0; }
inline void _out(bool x) { ptc(x ? '1' : '0'); }
void _out(int x) { if(x < 0) ptc('-'), x = -x; if(x > 9) _out(x / 10); ptc(x % 10 ^ '0'); }
void _out(unsigned int x) { if(x > 9) _out(x / 10); ptc(x % 10 ^ '0'); }
void _out(long long x) { if(x < 0) ptc('-'), x = -x; if(x > 9) _out(x / 10); ptc(x % 10 ^ '0'); }
void _out(unsigned long long x) { if(x > 9) _out(x / 10); ptc(x % 10 ^ '0'); }
inline void _out(double x, int n = 8) { if(x < 0) ptc('-'), x = -x; _out((LL)x), x -= (LL)x, ptc('.'); while(n--) x *= 10, _out(LL(x) % 10); }
inline void _out(const char ch) { ptc(ch); }
#ifdef TEBLE
inline void _out(const char *p) { while(*p) ptc(*p++); }
inline void _out(const string &s) { const char *p = s.c_str(); while(*p) ptc(*p++); }
#else
inline void _out(const char *p) { ptc(); fwrite(p, 1, strlen(p), stdout); }
inline void _out(const string &s) { ptc(); fwrite(s.c_str(), 1, s.size(), stdout); }
#endif
template<class T, class U>inline void _out(pair<T, U> x) { _out(x.ff), _out(' '), _out(x.ss); }
template<class T, class U, class O>inline void _out(triple<T, U, O> res) { _out(res.ff), _out(' '), _out(res.ss), _out(' '), _out(res.tt); }
// LOCAL debug and input **************************************************************************
#ifdef TEBLE
#define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0, __VA_ARGS__, 9, 8, 7, 6, 5, 4, 3, 2, 1))
#define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
#define VA_NUM_ARGS_IMPL(_0, _1, _2, _3, _4, _5, _6, _7, _8, _9, N, ...) N
#define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
#define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
#define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
#define macro_dispatcher___(macro, nargs) macro ## nargs
#define bug                         DEBUG("---------------")
#define DBN1(a)                     DEBUG(#a" =",(a))
#define DBN2(a,b)                   DEBUG(#a" =",(a),',',#b" =",(b))
#define DBN3(a,b,c)                 DEBUG(#a" =",(a),',',#b" =",(b),',',#c" =",(c))
#define DBN4(a,b,c,d)               DEBUG(#a" =",(a),',',#b" =",(b),',',#c" =",(c),',',#d" =",(d))
#define DBN5(a,b,c,d,e)             DEBUG(#a" =",(a),',',#b" =",(b),',',#c" =",(c),',',#d" =",(d),',',#e" =",(e))
#define DBN6(a,b,c,d,e,f)           DEBUG(#a" =",(a),',',#b" =",(b),',',#c" =",(c),',',#d" =",(d),',',#e" =",(e),',',#f" =",(f))
#define DBN7(a,b,c,d,e,f,g)         DEBUG(#a" =",(a),',',#b" =",(b),',',#c" =",(c),',',#d" =",(d),',',#e" =",(e),',',#f" =",(f),',',#g" =",(g))
#define DBN8(a,b,c,d,e,f,g,h)       DEBUG(#a" =",(a),',',#b" =",(b),',',#c" =",(c),',',#d" =",(d),',',#e" =",(e),',',#f" =",(f),',',#g" =",(g),',',#h" =",(h))
#define DBN9(a,b,c,d,e,f,g,h,i)     DEBUG(#a" =",(a),',',#b" =",(b),',',#c" =",(c),',',#d" =",(d),',',#e" =",(e),',',#f" =",(f),',',#g" =",(g),',',#h" =",(h),',',#i" =",(i))
#define DBN10(a,b,c,d,e,f,g,h,i,j)  DEBUG(#a" =",(a),',',#b" =",(b),',',#c" =",(c),',',#d" =",(d),',',#e" =",(e),',',#f" =",(f),',',#g" =",(g),',',#h" =",(h),',',#i" =",(i),',',#j" =",(j))
#define debug(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
static bool Sign;
inline void _DEBUG_() {}
void _DEBUG(bool &x) { _out(x ? "true" : "false"); }
void _DEBUG(int x) { _out(x); }
void _DEBUG(unsigned int x) { _out(x); }
void _DEBUG(long long x) { _out(x); }
void _DEBUG(unsigned long long x) { _out(x); }
void _DEBUG(double x) { _out(x); }
void _DEBUG(const char &x) { _out(x); }
void _DEBUG(const char *x) { _out(x); }
void _DEBUG(const string &x) { _out('\"'), _out(x), _out('\"'); }
bool __out(const char *p) { fwrite(p, 1, strlen(p), stdout); return 0; }
template<class T, class U>inline void _DEBUG(pair<T, U> &x) { _out('('), _DEBUG(x.ff), _out(", "), _DEBUG(x.ss), _out(')'); }
template<class T, class U, class O>inline void _DEBUG(triple<T, U, O> &x) { _out('('), _DEBUG(x.ff), _out(", "), _DEBUG(x.ss), _out(", "), _DEBUG(x.tt), _out(')'); }
template<class T>inline void _DEBUG(vector<T> &s) { _out('['); for(auto i = s.begin(); i != s.end(); ++i) _out(i == s.begin() ? "" : ", "), _DEBUG(*i); _out(']'); }
template<class T,class U,class O>inline void _DEBUG(const map<T, U, O> &s) { _out('['); for(auto i = s.begin(); i != s.end(); ++i) _out(i == s.begin() ? "(" : ", ("), _DEBUG(i->ff), _out(" -> "), _DEBUG(i->ss), _out(')'); _out(']'); }
template<class T,class U,class O>inline void _DEBUG(const multimap<T, U, O> &s) { _out('['); for(auto i = s.begin(); i != s.end(); ++i) _out(i == s.begin() ? "(" : ", ("), _DEBUG(i->ff), _out(" -> "), _DEBUG(i->ss), _out(')'); _out(']'); }
template<class T,class U>inline void _DEBUG(const unordered_map<T, U> &s) { _out('['); for(auto i = s.begin(); i != s.end(); ++i) _out(i == s.begin() ? "(" : ", ("), _DEBUG(i->ff), _out(" -> "), _DEBUG(i->ss), _out(')'); _out(']'); }
template<class T,class U>inline void _DEBUG(const set<T, U> &s) { _out('['); for(auto i = s.begin(); i != s.end(); ++i) _out(i == s.begin() ? "" : ", "), _DEBUG(*i); _out(']'); }
template<class T,class U>inline void _DEBUG(const multiset<T, U> &s) { _out('['); for(auto i = s.begin(); i != s.end(); ++i) _out(i == s.begin() ? "" : ", "), _DEBUG(*i); _out(']'); }
template<class T>inline void _DEBUG(const unordered_set<T> &s) { _out('['); for(auto i = s.begin(); i != s.end(); ++i) _out(i == s.begin() ? "" : ", "), _DEBUG(*i); _out(']'); }
template<class T,class U>inline void _DEBUG(priority_queue<T, U> s) { _out('['); while(!s.empty()) _DEBUG(s.top()),s.pop(), _out(s.empty() ? "" : ", "); _out(']'); }
template<class T, class ...U>void _DEBUG_(T head, U ...tail) { _out(' '), _DEBUG(head), _DEBUG_(tail...); }
template<class ...T>inline void DEBUG(T ...tail) { static int cnt = 0; Sign = 0; _DEBUG_("#####", ++cnt, '|', tail..., '\n'),ptc(); }
#define _read _scan
#define gts _gts
void scanbit(double &ret, char ch = getchar()) { if(isdigit(ch)) scanbit(ret), ret += ch ^ '0', ret *= 0.1; else chr = ch; }
inline bool _scan(int &res, bool flag = 0) { if(!Sign) __out(">>> "), Sign = 1; else if(chr == '\n') __out("... "); while(chr = getchar(), !isdigit(chr)) if(flag |= chr == '-', !~chr) return false; else if(chr == '\n') __out("... "); for(res = 0; isdigit(chr); res += res << 2, res <<= 1, res += chr ^ '0', chr = getchar()) ; flag && (res = -res); return true; }
inline bool _scan(unsigned int &res) { if(!Sign) __out(">>> "), Sign = 1; else if(chr == '\n') __out("... "); while(chr = getchar(), !isdigit(chr)) if(!~chr) return false; else if(chr == '\n') __out("... "); for(res = 0; isdigit(chr); res += res << 2, res <<= 1, res += chr ^ '0', chr = getchar()) ; return true; }
inline bool _scan(long long &res, bool flag = 0) { if(!Sign) __out(">>> "), Sign = 1; else if(chr == '\n') __out("... "); while(chr = getchar(), !isdigit(chr)) if(flag |= chr == '-', !~chr) return false; else if(chr == '\n') __out("... "); for(res = 0; isdigit(chr); res += res << 2, res <<= 1, res += chr ^ '0', chr = getchar()) ; flag && (res = -res); return true; }
inline bool _scan(unsigned long long &res) { if(!Sign) __out(">>> "), Sign = 1; else if(chr == '\n') __out("... "); while(chr = getchar(), !isdigit(chr)) if(!~chr) return false; else if(chr == '\n') __out("... "); for(res = 0; isdigit(chr); res += res << 2, res <<= 1, res += chr ^ '0', chr = getchar()) ; return true; }
inline bool _scan(double &ret, bool flag = 0, long long sum = 0) { if(!Sign) __out(">>> "), Sign = 1; else if(chr == '\n') __out("... "); while(chr = getchar(), !isdigit(chr)) if(flag |= chr == '-', !~chr) return false; else if(chr == '\n') __out("... ");debug(chr); while(isdigit(chr)) sum += sum << 2, sum <<= 1, sum += chr ^ '0', chr = getchar(); if(ret = 0, chr == '.') scanbit(ret), ret += 1e-9; ret += sum, flag && (ret = -ret); return true; }
inline bool _scan(char &chr) { if(chr == '\n' && Sign) __out("... "); Sign ? 0 : __out(">>> "), Sign = 1; while(chr = getchar(), (chr == ' ') || (chr == '\n') || (!~chr)) if(!~chr) return 0; return 1; }
inline bool _scan(char *p) { if(chr == '\n' && Sign) __out("... "); Sign ? 0 : __out(">>> "), Sign = 1; while(chr = getchar(), (chr == ' ') || (chr == '\n') || (!~chr)) if(!~chr) return 0; else if(chr == '\n') __out("... "); while(chr ^ '\n' && chr ^ ' ' && chr) *p++ = chr, chr = getchar(); *p = 0; return 1; }
inline bool _scan(string &s) { if(chr == '\n' && Sign) __out("... "); Sign ? 0 : __out(">>> "), Sign = 1; s.reserve(256); s.clear(); while(chr = getchar(), (chr == ' ') || (chr == '\n') || (!~chr)) if(!~chr) return 0; else if(chr == '\n') __out("... "); *en = 0; while(chr ^ '\n' && chr ^ ' ' && chr) *be++ = chr, be != en ? chr = getchar() : (be = _s, s.append(_s, en), chr = getchar()); *be=0, s.append(_s, be), be = _s; return 1; }
inline bool _gts(char *p) { if(chr == '\n' && Sign) __out("... "); Sign ? 0 : __out(">>> "), Sign = 1; while(chr = getchar(), (!~chr)) if(!~chr) return 0; while(chr ^ '\n' && chr) *p++ = chr, chr = getchar(); *p = 0; return 1; }
inline bool _gts(string &s) { if(chr == '\n' && Sign) __out("... "); Sign ? 0 : __out(">>> "), Sign = 1; s.reserve(256), s.clear(); while(chr = getchar(), (!~chr)) if(!~chr) return 0; *en = 0; while(chr ^ '\n' && chr) *be++ = chr, be < en ? chr = getchar() : (be = _s, s.append(_s, en), chr = getchar()); *be = 0, s.append(_s, be), be = _s; return 1; }
template<class T, class U>inline bool _scan(pair<T, U> &res) { return _scan(res.ff), _scan(res.ss); }
template<class T, class U, class O >inline bool _scan(triple<T, U, O> &res) { return _scan(res.ff), _scan(res.ss), _scan(res.tt); }
struct basic_io { bool flag, lock; basic_io() : lock(0) {} void tie(bool x) { lock = x; } template<class T>inline basic_io& operator >> (T &x) { return flag = _read(x), *this; } template<class T>inline basic_io& operator >> (T *x) { return flag = _read(x), *this; } operator void *() const { return flag ? (void*)this : 0; } template<class T>inline basic_io& operator << (const T& x) { return Sign = 0, _out(x), lock ? (ptc(), 0) : 0, *this; } inline basic_io& operator << (basic_io& (*op)(basic_io&)) { return (*op)(*this); } ~basic_io() { ptc(); } } IO;
inline basic_io& io_endl(basic_io & strm) { return Sign = 0, _out('\n'), IO.lock ? (ptc(), 0) : 0, strm; }
#else
struct basic_io { bool flag; template<class T>inline basic_io& operator >> (T &x) { return flag = _read(x), *this; } template<class T>inline basic_io& operator >> (T *x) { return flag = _read(x), *this; } operator void *() const { return flag ? (void*)this : 0; } template<class T>inline basic_io& operator << (const T& x) { return _out(x), *this; } basic_io& operator << (basic_io& (*op)(basic_io&)) { return (*op)(*this); } ~basic_io() { ptc(); } } IO;
inline basic_io& io_endl(basic_io & strm) { return _out('\n'), strm; }
#endif
// STL other **************************************************************************************
template<class T, class U>inline istream& operator >> (istream& os, pair<T, U>& p) { return os >> p.first >> p.second; }
template<class T, class U>inline ostream& operator << (ostream& os, const pair<T, U>& p) { return os << p.first << ' ' << p.second; }
template<class T, class U, class O>inline istream& operator >> (istream& os, triple<T, U, O>& t) { return os >> t.first >> t.second >> t.third; }
template<class T, class U, class O>inline ostream& operator << (ostream& os, const triple<T, U, O>& t) { return os << t.first << ' ' << t.second << ' ' << t.third; }
template<class T, class U>inline pair<T, U> operator + (const pair<T, U>& p1, const pair<T, U>& p2) { return mp(p1.ff + p2.ff, p1.ss + p2.ss); }
template<class T, class U>inline pair<T, U>& operator += (pair<T, U>& p1, const pair<T, U>& p2) { p1.ff += p2.ff, p1.ss += p2.ss; return p1; }
template<class T, class U>inline pair<T, U> operator - (const pair<T, U>& p1, const pair<T, U>& p2) { return mp(p1.ff - p2.ff, p1.ss - p2.ss); }
template<class T, class U>inline pair<T, U>& operator -= (pair<T, U>& p1, const pair<T, U>& p2) { p1.ff -= p2.ff, p1.ss -= p2.ss; return p1; }
// Useful constants *******************************************************************************

const int       primes[7] = {24443, 100271, 1000003, 1000333, 5000321, 98765431, 1000000123};
const int       dx[] = { 0, 1, 0,-1, 0, 1,-1, 1,-1};
const int       dy[] = {-1, 0, 1, 0,-1, 1,-1,-1, 1};
#define ee      2.718281828459
#define eps     0.00000001
#define fftmod  998244353
#define INF     0x3f3f3f3f
#define LINF    0x3f3f3f3f3f3f3f3fll
#define MOD     1000000007
#define pi      3.14159265358979323846l
#define ing     int
// My function ************************************************************************************
inline int myrand(int mod) { return (((LL)rand() << 16) | ((LL)rand())) % mod; }
inline int rand(int a, int b) { return a + myrand(b - a + 1); }
#if __cplusplus >= 201103L
inline function<int()> randi(int a, int b) { static random_device rd; static mt19937 gen(rd()); uniform_int_distribution<int> dis(a, b); return bind(dis, gen); }
inline function<long long()> randl(long long a, long long b) { static random_device rd; static mt19937_64 gen(rd()); uniform_int_distribution<long long> dis(a, b); return bind(dis, gen); }
template<class T, class U, class O>constexpr triple<typename __decay_and_strip<T>::__type, typename __decay_and_strip<U>::__type, typename __decay_and_strip<O>::__type> make_triple(T&& __x, U&& __y, O&& __z) { return triple<typename __decay_and_strip<T>::__type, typename __decay_and_strip<U>::__type, typename __decay_and_strip<O>::__type>(std::forward<T>(__x), std::forward<U>(__y), std::forward<O>(__z)); }
#else
template<class T, class U, class O>inline triple<T, U, O> make_triple(T _x, U _y, O _z) { return triple<T, U, O>(_x, _y, _z); }
#endif
inline void normmod(long long &x, long long mod = MOD) { (x %= mod) < 0 ? x += mod: 0; }
inline long long mulmod(long long x, long long n,long long mod = MOD) { long long ans=(x*n-(long long)((long double)x/mod*n+eps)*mod); return ans < 0 ? ans + mod : ans; }
inline long long pmod(long long x, long long n, long long mod = MOD, long long res = 1) { for(normmod(x, mod); n; x = x * x % mod, n >>= 1) n & 1 ? res = res * x % mod : 0; return res; }
inline long long pmmod(long long x, long long n, long long mod = MOD, long long res = 1) { for(normmod(x, mod); n; x = mulmod(x, x, mod), n >>= 1) n & 1 ? res = mulmod(res, x, mod) : 0; return res; }
template<class T>inline T gcd(T a, T b) { while(b) { T t = a % b; a = b, b = t; } return a; }
template<class T>inline T gcd(T a, T b, T c) { return gcd(a, gcd(b, c)); }
template<class T>inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
template<class T>inline T lcm(T a, T b, T c) { lcm(a, lcm(b, c)); }
//*************************************************************************************************

void teble();
int main() {
#if 1
    #define cin IO
    #define cout IO
    #define endl '\n'
    #define gets(a) gts(a)
//    #define int LL
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
#ifdef TEBLE
    IO.tie(1);
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
#else
    #define debug(...) 0
    #define bug 0
#endif
    teble();
    return 0;
}
//***************************************************************
//***************************************************************
//***************************************************************
/**________________________code.begin_________________________**/

const int N=1e3+5;

void teble() {
    string a;
    cin>>a;
    int b=0,c=0;
    FOR(i,2,a.size()-2)if(a[i]=='C')++b;
    FOR(i,0,a.size()-1)if(a[i]!='A'&&a[i]!='C')if(a[i]>='A'&&a[i]<='Z')++c;
    if(a[0]=='A'&&b==1&&c==0)cout<<"AC";
    else cout<<"WA"<<endl;
}

/**_________________________code.end__________________________**/
//***************************************************************
//***************************************************************
//***************************************************************
/****************************************************************
**                                                             **
**  *********   *********   ********    **          *********  **
**      **      **          **     **   **          **         **
**      **      **          **     **   **          **         **
**      **      *********   ********    **          *********  **
**      **      **          **     **   **          **         **
**      **      **          **     **   **          **         **
**      **      *********   ********    *********   *********  **
**                                                             **
****************************************************************/


Measured memory_bytes: 256