#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
const int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 200005;
const ld PI = 4*atan((ld)1);
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
namespace input {
template<class T> void re(complex<T>& x);
template<class T1, class T2> void re(pair<T1,T2>& p);
template<class T> void re(vector<T>& a);
template<class T, size_t SZ> void re(array<T,SZ>& a);
template<class T> void re(T& x) { cin >> x; }
void re(double& x) { string t; re(t); x = stod(t); }
void re(ld& x) { string t; re(t); x = stold(t); }
template<class Arg, class... Args> void re(Arg& first, Args&... rest) {
re(first); re(rest...);
}
template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}
using namespace input;
namespace output {
template<class T1, class T2> void pr(const pair<T1,T2>& x);
template<class T, size_t SZ> void pr(const array<T,SZ>& x);
template<class T> void pr(const vector<T>& x);
template<class T> void pr(const set<T>& x);
template<class T1, class T2> void pr(const map<T1,T2>& x);
template<class T> void pr(const T& x) { cout << x; }
template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
pr(first); pr(rest...);
}
template<class T1, class T2> void pr(const pair<T1,T2>& x) {
pr("{",x.f,", ",x.s,"}");
}
template<class T> void prContain(const T& x) {
pr("{");
bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; // const needed for vector<bool>
pr("}");
}
template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
template<class T> void pr(const vector<T>& x) { prContain(x); }
template<class T> void pr(const set<T>& x) { prContain(x); }
template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
void ps() { pr("\n"); }
template<class Arg> void ps(const Arg& first) {
pr(first); ps(); // no space at end of line
}
template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
pr(first," "); ps(rest...); // print w/ spaces
}
}
using namespace output;
namespace io {
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
}
using namespace io;
template<class T> T invGeneral(T a, T b) {
a %= b; if (a == 0) return b == 1 ? 0 : -1;
T x = invGeneral(b,a);
return x == -1 ? -1 : ((1-(ll)b*x)/a+b)%b;
}
template<class T> struct modular {
T val;
explicit operator T() const { return val; }
modular() { val = 0; }
modular(const ll& v) {
val = (-MOD <= v && v <= MOD) ? v : v % MOD;
if (val < 0) val += MOD;
}
friend ostream& operator<<(ostream& os, const modular& a) { return os << a.val; }
friend bool operator==(const modular& a, const modular& b) { return a.val == b.val; }
friend bool operator!=(const modular& a, const modular& b) { return !(a == b); }
modular operator-() const { return modular(-val); }
modular& operator+=(const modular& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
modular& operator-=(const modular& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
modular& operator*=(const modular& m) { val = (ll)val*m.val%MOD; return *this; }
friend modular pow(modular a, ll p) {
modular ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans;
}
friend modular inv(const modular& a) {
auto i = invGeneral(a.val,MOD); assert(i != -1);
return i;
} // equivalent to return exp(b,MOD-2) if MOD is prime
modular& operator/=(const modular& m) { return (*this) *= inv(m); }
friend modular operator+(modular a, const modular& b) { return a += b; }
friend modular operator-(modular a, const modular& b) { return a -= b; }
friend modular operator*(modular a, const modular& b) { return a *= b; }
friend modular operator/(modular a, const modular& b) { return a /= b; }
};
typedef modular<int> mi;
typedef pair<mi,mi> pmi;
typedef vector<mi> vmi;
typedef vector<pmi> vpmi;
int M,R,C,mx[1<<4];
pi ans = {MOD,MOD};
vector<vi> U;
int comp[800][800], par[800*800];
vpi rcomp[800*800];
string dir = "ENWS";
int xd[4] = {0,1,0,-1}, yd[4] = {-1,0,1,0};
string D;
int hsh(int a, int b) { return C*a+b; }
bool sat(char a, int b) {
int pos = dir.find(a);
return b&(1<<pos);
}
int con(int x) {
int ret = 0;
for (int i = 0; i < sz(D); ) {
if (!sat(D[i],x)) i++;
else {
int I = i;
while (i < sz(D) && sat(D[i],x)) i ++;
if (I == 0 && i == sz(D)) return MOD;
ckmax(ret,i-I);
}
}
return ret;
}
void init() {
setIO(); re(M,R,C,D); D += D;
F0R(i,1<<4) {
mx[i] = con(i);
// ps(i,mx[i]);
}
U.rsz(R);
F0R(i,R*C) par[i] = -1;
F0R(i,R) {
U[i].rsz(C); re(U[i]);
F0R(j,C) if (U[i][j]) {
int x = C*i+j; comp[i][j] = x+MOD;
rcomp[x].pb({i,j}); par[x] = x;
} else comp[i][j] = -MOD;
}
}
int get(int x) {
if (x == -1) return x;
if (par[x] == x) return x;
return par[x] = get(par[x]);
}
int cnt = 0;
int vis[800][800];
pi st[800][800];
bool valid(pi A) {
if (A.f < 0 || A.f >= R || A.s < 0 || A.s >= C) return 0;
if (U[A.f][A.s] == 0) return 0;
return 1;
}
int getComp(pi A) {
int t = comp[A.f][A.s]; if (t >= MOD) t -= MOD;
return t;
}
pi bfs(pi x) {
assert(comp[x.f][x.s] >= MOD);
queue<pi> q;
vis[x.f][x.s] = ++cnt; q.push(x);
int num = 1;
while (sz(q)) {
auto a = q.front(); q.pop();
F0R(i,4) {
pi A = {a.f+xd[i],a.s+yd[i]};
if (!valid(A) || vis[A.f][A.s] == cnt) continue;
if (st[A.f][A.s].f != cnt) st[A.f][A.s] = {cnt,0};
st[A.f][A.s].s |= 1<<i;
if (mx[st[A.f][A.s].s] >= U[A.f][A.s]) {
num ++; vis[A.f][A.s] = cnt; q.push(A);
if (getComp(A) != comp[x.f][x.s]-MOD) return {getComp(A),num};
}
}
}
return {MOD,num};
}
void join(int a, int b) {
a = get(a), b = get(b);
if (a == b) return;
assert(a != -1);
if (b == -1) {
trav(t,rcomp[a]) comp[t.f][t.s] = -1;
par[a] = b; rcomp[a].clear();
return;
}
if (sz(rcomp[a]) > sz(rcomp[b])) {
pi A = rcomp[a].back(); comp[A.f][A.s] = a;
trav(t,rcomp[b]) {
comp[t.f][t.s] = a;
rcomp[a].pb(t);
}
A = rcomp[a].back(); comp[A.f][A.s] = a+MOD;
par[b] = a; rcomp[b].clear();
} else {
int ind = sz(rcomp[b])-1;
trav(t,rcomp[a]) {
comp[t.f][t.s] = b;
rcomp[b].pb(t);
}
swap(rcomp[b][ind],rcomp[b].back());
par[a] = b; rcomp[a].clear();
}
}
int main() {
init();
F0R(i,100) {
vpi ed;
F0R(i,R) F0R(j,C) if (comp[i][j] >= MOD) { // special cell
int c = comp[i][j]-MOD;
pi x = bfs({i,j});
if (x.f == MOD) { // no new component reached, update answer
if (ans.f > x.s) ans = {x.s,0};
if (ans.f == x.s) ans.s += x.s;
ed.pb({c,-1});
} else if (x.f == -1) {
ed.pb({c,-1});
} else ed.pb({c,x.f});
}
if (!sz(ed)) break;
trav(t,ed) {
join(t.f,t.s); // merge components
}
}
ps(ans.f,ans.s);
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?), set tle
* do smth instead of nothing and stay organized
*/
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPMyIpCiNwcmFnbWEgR0NDIHRhcmdldCAoInNzZTQiKQoKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvdHJlZV9wb2xpY3kuaHBwPgojaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+CiNpbmNsdWRlIDxleHQvcm9wZT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwp1c2luZyBuYW1lc3BhY2UgX19nbnVfY3h4OwogCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwp0eXBlZGVmIGNvbXBsZXg8bGQ+IGNkOwoKdHlwZWRlZiBwYWlyPGludCwgaW50PiBwaTsKdHlwZWRlZiBwYWlyPGxsLGxsPiBwbDsKdHlwZWRlZiBwYWlyPGxkLGxkPiBwZDsKCnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPGxkPiB2ZDsKdHlwZWRlZiB2ZWN0b3I8bGw+IHZsOwp0eXBlZGVmIHZlY3RvcjxwaT4gdnBpOwp0eXBlZGVmIHZlY3RvcjxwbD4gdnBsOwp0eXBlZGVmIHZlY3RvcjxjZD4gdmNkOwoKdGVtcGxhdGUgPGNsYXNzIFQ+IHVzaW5nIFRyZWUgPSB0cmVlPFQsIG51bGxfdHlwZSwgbGVzczxUPiwgcmJfdHJlZV90YWcsdHJlZV9vcmRlcl9zdGF0aXN0aWNzX25vZGVfdXBkYXRlPjsKCiNkZWZpbmUgRk9SKGksIGEsIGIpIGZvciAoaW50IGkgPSAoYSk7IGkgPCAoYik7IGkrKykKI2RlZmluZSBGMFIoaSwgYSkgZm9yIChpbnQgaSA9IDA7IGkgPCAoYSk7IGkrKykKI2RlZmluZSBGT1JkKGksYSxiKSBmb3IgKGludCBpID0gKGIpLTE7IGkgPj0gKGEpOyBpLS0pCiNkZWZpbmUgRjBSZChpLGEpIGZvciAoaW50IGkgPSAoYSktMTsgaSA+PSAwOyBpLS0pCiNkZWZpbmUgdHJhdihhLCB4KSBmb3IgKGF1dG8mIGEgOiB4KQoKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBmIGZpcnN0CiNkZWZpbmUgcyBzZWNvbmQKI2RlZmluZSBsYiBsb3dlcl9ib3VuZAojZGVmaW5lIHViIHVwcGVyX2JvdW5kCgojZGVmaW5lIHN6KHgpIChpbnQpeC5zaXplKCkKI2RlZmluZSBhbGwoeCkgYmVnaW4oeCksIGVuZCh4KQojZGVmaW5lIHJzeiByZXNpemUKCmNvbnN0IGludCBNT0QgPSAxMDAwMDAwMDA3OyAvLyA5OTgyNDQzNTMKY29uc3QgbGwgSU5GID0gMWUxODsKY29uc3QgaW50IE1YID0gMjAwMDA1Owpjb25zdCBsZCBQSSA9IDQqYXRhbigobGQpMSk7Cgp0ZW1wbGF0ZTxjbGFzcyBUPiB2b2lkIGNrbWluKFQgJmEsIFQgYikgeyBhID0gbWluKGEsIGIpOyB9CnRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgY2ttYXgoVCAmYSwgVCBiKSB7IGEgPSBtYXgoYSwgYik7IH0KCm5hbWVzcGFjZSBpbnB1dCB7CiAgICB0ZW1wbGF0ZTxjbGFzcyBUPiB2b2lkIHJlKGNvbXBsZXg8VD4mIHgpOwogICAgdGVtcGxhdGU8Y2xhc3MgVDEsIGNsYXNzIFQyPiB2b2lkIHJlKHBhaXI8VDEsVDI+JiBwKTsKICAgIHRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgcmUodmVjdG9yPFQ+JiBhKTsKICAgIHRlbXBsYXRlPGNsYXNzIFQsIHNpemVfdCBTWj4gdm9pZCByZShhcnJheTxULFNaPiYgYSk7CgogICAgdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCByZShUJiB4KSB7IGNpbiA+PiB4OyB9CiAgICB2b2lkIHJlKGRvdWJsZSYgeCkgeyBzdHJpbmcgdDsgcmUodCk7IHggPSBzdG9kKHQpOyB9CiAgICB2b2lkIHJlKGxkJiB4KSB7IHN0cmluZyB0OyByZSh0KTsgeCA9IHN0b2xkKHQpOyB9CiAgICB0ZW1wbGF0ZTxjbGFzcyBBcmcsIGNsYXNzLi4uIEFyZ3M+IHZvaWQgcmUoQXJnJiBmaXJzdCwgQXJncyYuLi4gcmVzdCkgeyAKICAgICAgICByZShmaXJzdCk7IHJlKHJlc3QuLi4pOyAKICAgIH0KCiAgICB0ZW1wbGF0ZTxjbGFzcyBUPiB2b2lkIHJlKGNvbXBsZXg8VD4mIHgpIHsgVCBhLGI7IHJlKGEsYik7IHggPSBjZChhLGIpOyB9CiAgICB0ZW1wbGF0ZTxjbGFzcyBUMSwgY2xhc3MgVDI+IHZvaWQgcmUocGFpcjxUMSxUMj4mIHApIHsgcmUocC5mLHAucyk7IH0KICAgIHRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgcmUodmVjdG9yPFQ+JiBhKSB7IEYwUihpLHN6KGEpKSByZShhW2ldKTsgfQogICAgdGVtcGxhdGU8Y2xhc3MgVCwgc2l6ZV90IFNaPiB2b2lkIHJlKGFycmF5PFQsU1o+JiBhKSB7IEYwUihpLFNaKSByZShhW2ldKTsgfQp9Cgp1c2luZyBuYW1lc3BhY2UgaW5wdXQ7CgpuYW1lc3BhY2Ugb3V0cHV0IHsKICAgIHRlbXBsYXRlPGNsYXNzIFQxLCBjbGFzcyBUMj4gdm9pZCBwcihjb25zdCBwYWlyPFQxLFQyPiYgeCk7CiAgICB0ZW1wbGF0ZTxjbGFzcyBULCBzaXplX3QgU1o+IHZvaWQgcHIoY29uc3QgYXJyYXk8VCxTWj4mIHgpOwogICAgdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCBwcihjb25zdCB2ZWN0b3I8VD4mIHgpOwogICAgdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCBwcihjb25zdCBzZXQ8VD4mIHgpOwogICAgdGVtcGxhdGU8Y2xhc3MgVDEsIGNsYXNzIFQyPiB2b2lkIHByKGNvbnN0IG1hcDxUMSxUMj4mIHgpOwoKICAgIHRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgcHIoY29uc3QgVCYgeCkgeyBjb3V0IDw8IHg7IH0KICAgIHRlbXBsYXRlPGNsYXNzIEFyZywgY2xhc3MuLi4gQXJncz4gdm9pZCBwcihjb25zdCBBcmcmIGZpcnN0LCBjb25zdCBBcmdzJi4uLiByZXN0KSB7IAogICAgICAgIHByKGZpcnN0KTsgcHIocmVzdC4uLik7IAogICAgfQoKICAgIHRlbXBsYXRlPGNsYXNzIFQxLCBjbGFzcyBUMj4gdm9pZCBwcihjb25zdCBwYWlyPFQxLFQyPiYgeCkgeyAKICAgICAgICBwcigieyIseC5mLCIsICIseC5zLCJ9Iik7IAogICAgfQogICAgdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCBwckNvbnRhaW4oY29uc3QgVCYgeCkgewogICAgICAgIHByKCJ7Iik7CiAgICAgICAgYm9vbCBmc3QgPSAxOyBmb3IgKGNvbnN0IGF1dG8mIGE6IHgpIHByKCFmc3Q/IiwgIjoiIixhKSwgZnN0ID0gMDsgLy8gY29uc3QgbmVlZGVkIGZvciB2ZWN0b3I8Ym9vbD4KICAgICAgICBwcigifSIpOwogICAgfQogICAgdGVtcGxhdGU8Y2xhc3MgVCwgc2l6ZV90IFNaPiB2b2lkIHByKGNvbnN0IGFycmF5PFQsU1o+JiB4KSB7IHByQ29udGFpbih4KTsgfQogICAgdGVtcGxhdGU8Y2xhc3MgVD4gdm9pZCBwcihjb25zdCB2ZWN0b3I8VD4mIHgpIHsgcHJDb250YWluKHgpOyB9CiAgICB0ZW1wbGF0ZTxjbGFzcyBUPiB2b2lkIHByKGNvbnN0IHNldDxUPiYgeCkgeyBwckNvbnRhaW4oeCk7IH0KICAgIHRlbXBsYXRlPGNsYXNzIFQxLCBjbGFzcyBUMj4gdm9pZCBwcihjb25zdCBtYXA8VDEsVDI+JiB4KSB7IHByQ29udGFpbih4KTsgfQogICAgCiAgICB2b2lkIHBzKCkgeyBwcigiXG4iKTsgfQogICAgdGVtcGxhdGU8Y2xhc3MgQXJnPiB2b2lkIHBzKGNvbnN0IEFyZyYgZmlyc3QpIHsgCiAgICAgICAgcHIoZmlyc3QpOyBwcygpOyAvLyBubyBzcGFjZSBhdCBlbmQgb2YgbGluZQogICAgfQogICAgdGVtcGxhdGU8Y2xhc3MgQXJnLCBjbGFzcy4uLiBBcmdzPiB2b2lkIHBzKGNvbnN0IEFyZyYgZmlyc3QsIGNvbnN0IEFyZ3MmLi4uIHJlc3QpIHsgCiAgICAgICAgcHIoZmlyc3QsIiAiKTsgcHMocmVzdC4uLik7IC8vIHByaW50IHcvIHNwYWNlcwogICAgfQp9Cgp1c2luZyBuYW1lc3BhY2Ugb3V0cHV0OwoKbmFtZXNwYWNlIGlvIHsKICAgIHZvaWQgc2V0SW4oc3RyaW5nIHMpIHsgZnJlb3BlbihzLmNfc3RyKCksInIiLHN0ZGluKTsgfQogICAgdm9pZCBzZXRPdXQoc3RyaW5nIHMpIHsgZnJlb3BlbihzLmNfc3RyKCksInciLHN0ZG91dCk7IH0KICAgIHZvaWQgc2V0SU8oc3RyaW5nIHMgPSAiIikgewogICAgICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IC8vIGZhc3QgSS9PCiAgICAgICAgaWYgKHN6KHMpKSB7IHNldEluKHMrIi5pbiIpLCBzZXRPdXQocysiLm91dCIpOyB9IC8vIGZvciBVU0FDTwogICAgfQp9Cgp1c2luZyBuYW1lc3BhY2UgaW87Cgp0ZW1wbGF0ZTxjbGFzcyBUPiBUIGludkdlbmVyYWwoVCBhLCBUIGIpIHsKICAgIGEgJT0gYjsgaWYgKGEgPT0gMCkgcmV0dXJuIGIgPT0gMSA/IDAgOiAtMTsKICAgIFQgeCA9IGludkdlbmVyYWwoYixhKTsgCiAgICByZXR1cm4geCA9PSAtMSA/IC0xIDogKCgxLShsbCliKngpL2ErYiklYjsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4gc3RydWN0IG1vZHVsYXIgewogICAgVCB2YWw7IAogICAgZXhwbGljaXQgb3BlcmF0b3IgVCgpIGNvbnN0IHsgcmV0dXJuIHZhbDsgfQogICAgbW9kdWxhcigpIHsgdmFsID0gMDsgfQogICAgbW9kdWxhcihjb25zdCBsbCYgdikgeyAKICAgICAgICB2YWwgPSAoLU1PRCA8PSB2ICYmIHYgPD0gTU9EKSA/IHYgOiB2ICUgTU9EOwogICAgICAgIGlmICh2YWwgPCAwKSB2YWwgKz0gTU9EOwogICAgfQogICAgCiAgICBmcmllbmQgb3N0cmVhbSYgb3BlcmF0b3I8PChvc3RyZWFtJiBvcywgY29uc3QgbW9kdWxhciYgYSkgeyByZXR1cm4gb3MgPDwgYS52YWw7IH0KICAgIGZyaWVuZCBib29sIG9wZXJhdG9yPT0oY29uc3QgbW9kdWxhciYgYSwgY29uc3QgbW9kdWxhciYgYikgeyByZXR1cm4gYS52YWwgPT0gYi52YWw7IH0KICAgIGZyaWVuZCBib29sIG9wZXJhdG9yIT0oY29uc3QgbW9kdWxhciYgYSwgY29uc3QgbW9kdWxhciYgYikgeyByZXR1cm4gIShhID09IGIpOyB9CgogICAgbW9kdWxhciBvcGVyYXRvci0oKSBjb25zdCB7IHJldHVybiBtb2R1bGFyKC12YWwpOyB9CiAgICBtb2R1bGFyJiBvcGVyYXRvcis9KGNvbnN0IG1vZHVsYXImIG0pIHsgaWYgKCh2YWwgKz0gbS52YWwpID49IE1PRCkgdmFsIC09IE1PRDsgcmV0dXJuICp0aGlzOyB9CiAgICBtb2R1bGFyJiBvcGVyYXRvci09KGNvbnN0IG1vZHVsYXImIG0pIHsgaWYgKCh2YWwgLT0gbS52YWwpIDwgMCkgdmFsICs9IE1PRDsgcmV0dXJuICp0aGlzOyB9CiAgICBtb2R1bGFyJiBvcGVyYXRvcio9KGNvbnN0IG1vZHVsYXImIG0pIHsgdmFsID0gKGxsKXZhbCptLnZhbCVNT0Q7IHJldHVybiAqdGhpczsgfQogICAgZnJpZW5kIG1vZHVsYXIgcG93KG1vZHVsYXIgYSwgbGwgcCkgewogICAgICAgIG1vZHVsYXIgYW5zID0gMTsgZm9yICg7IHA7IHAgLz0gMiwgYSAqPSBhKSBpZiAocCYxKSBhbnMgKj0gYTsKICAgICAgICByZXR1cm4gYW5zOwogICAgfQogICAgZnJpZW5kIG1vZHVsYXIgaW52KGNvbnN0IG1vZHVsYXImIGEpIHsgCiAgICAgICAgYXV0byBpID0gaW52R2VuZXJhbChhLnZhbCxNT0QpOyBhc3NlcnQoaSAhPSAtMSk7CiAgICAgICAgcmV0dXJuIGk7CiAgICB9IC8vIGVxdWl2YWxlbnQgdG8gcmV0dXJuIGV4cChiLE1PRC0yKSBpZiBNT0QgaXMgcHJpbWUKICAgIG1vZHVsYXImIG9wZXJhdG9yLz0oY29uc3QgbW9kdWxhciYgbSkgeyByZXR1cm4gKCp0aGlzKSAqPSBpbnYobSk7IH0KICAgIAogICAgZnJpZW5kIG1vZHVsYXIgb3BlcmF0b3IrKG1vZHVsYXIgYSwgY29uc3QgbW9kdWxhciYgYikgeyByZXR1cm4gYSArPSBiOyB9CiAgICBmcmllbmQgbW9kdWxhciBvcGVyYXRvci0obW9kdWxhciBhLCBjb25zdCBtb2R1bGFyJiBiKSB7IHJldHVybiBhIC09IGI7IH0KICAgIGZyaWVuZCBtb2R1bGFyIG9wZXJhdG9yKihtb2R1bGFyIGEsIGNvbnN0IG1vZHVsYXImIGIpIHsgcmV0dXJuIGEgKj0gYjsgfQogICAgCiAgICBmcmllbmQgbW9kdWxhciBvcGVyYXRvci8obW9kdWxhciBhLCBjb25zdCBtb2R1bGFyJiBiKSB7IHJldHVybiBhIC89IGI7IH0KfTsKCnR5cGVkZWYgbW9kdWxhcjxpbnQ+IG1pOwp0eXBlZGVmIHBhaXI8bWksbWk+IHBtaTsKdHlwZWRlZiB2ZWN0b3I8bWk+IHZtaTsKdHlwZWRlZiB2ZWN0b3I8cG1pPiB2cG1pOwoKaW50IE0sUixDLG14WzE8PDRdOwpwaSBhbnMgPSB7TU9ELE1PRH07CnZlY3Rvcjx2aT4gVTsKaW50IGNvbXBbODAwXVs4MDBdLCBwYXJbODAwKjgwMF07CnZwaSByY29tcFs4MDAqODAwXTsKCnN0cmluZyBkaXIgPSAiRU5XUyI7CmludCB4ZFs0XSA9IHswLDEsMCwtMX0sIHlkWzRdID0gey0xLDAsMSwwfTsKc3RyaW5nIEQ7CgppbnQgaHNoKGludCBhLCBpbnQgYikgeyByZXR1cm4gQyphK2I7IH0KCmJvb2wgc2F0KGNoYXIgYSwgaW50IGIpIHsKCWludCBwb3MgPSBkaXIuZmluZChhKTsKCXJldHVybiBiJigxPDxwb3MpOwp9CgppbnQgY29uKGludCB4KSB7CglpbnQgcmV0ID0gMDsKCWZvciAoaW50IGkgPSAwOyBpIDwgc3ooRCk7ICkgewoJCWlmICghc2F0KERbaV0seCkpIGkrKzsKCQllbHNlIHsKCQkJaW50IEkgPSBpOwoJCQl3aGlsZSAoaSA8IHN6KEQpICYmIHNhdChEW2ldLHgpKSBpICsrOwoJCQlpZiAoSSA9PSAwICYmIGkgPT0gc3ooRCkpIHJldHVybiBNT0Q7CgkJCWNrbWF4KHJldCxpLUkpOwoJCX0KCX0KCXJldHVybiByZXQ7Cn0KCnZvaWQgaW5pdCgpIHsKICAgIHNldElPKCk7IHJlKE0sUixDLEQpOyBEICs9IEQ7CiAgICBGMFIoaSwxPDw0KSB7CiAgICAJbXhbaV0gPSBjb24oaSk7CiAgICAJLy8gcHMoaSxteFtpXSk7CiAgICB9CiAgICBVLnJzeihSKTsKICAgIEYwUihpLFIqQykgcGFyW2ldID0gLTE7CiAgICBGMFIoaSxSKSB7CiAgICAJVVtpXS5yc3ooQyk7IHJlKFVbaV0pOwogICAgCUYwUihqLEMpIGlmIChVW2ldW2pdKSB7CiAgICAJCWludCB4ID0gQyppK2o7IGNvbXBbaV1bal0gPSB4K01PRDsKICAgIAkJcmNvbXBbeF0ucGIoe2ksan0pOyBwYXJbeF0gPSB4OwogICAgCX0gZWxzZSBjb21wW2ldW2pdID0gLU1PRDsKICAgIH0KfQoKaW50IGdldChpbnQgeCkgewoJaWYgKHggPT0gLTEpIHJldHVybiB4OwoJaWYgKHBhclt4XSA9PSB4KSByZXR1cm4geDsKCXJldHVybiBwYXJbeF0gPSBnZXQocGFyW3hdKTsKfQoKaW50IGNudCA9IDA7CmludCB2aXNbODAwXVs4MDBdOwpwaSBzdFs4MDBdWzgwMF07Cgpib29sIHZhbGlkKHBpIEEpIHsKCWlmIChBLmYgPCAwIHx8IEEuZiA+PSBSIHx8IEEucyA8IDAgfHwgQS5zID49IEMpIHJldHVybiAwOwoJaWYgKFVbQS5mXVtBLnNdID09IDApIHJldHVybiAwOwoJcmV0dXJuIDE7Cn0KCmludCBnZXRDb21wKHBpIEEpIHsKCWludCB0ID0gY29tcFtBLmZdW0Euc107IGlmICh0ID49IE1PRCkgdCAtPSBNT0Q7CglyZXR1cm4gdDsKfQoKcGkgYmZzKHBpIHgpIHsKCWFzc2VydChjb21wW3guZl1beC5zXSA+PSBNT0QpOwoJcXVldWU8cGk+IHE7IAoJdmlzW3guZl1beC5zXSA9ICsrY250OyBxLnB1c2goeCk7CglpbnQgbnVtID0gMTsKCXdoaWxlIChzeihxKSkgewoJCWF1dG8gYSA9IHEuZnJvbnQoKTsgcS5wb3AoKTsKCQlGMFIoaSw0KSB7CgkJCXBpIEEgPSB7YS5mK3hkW2ldLGEucyt5ZFtpXX07IAoJCQlpZiAoIXZhbGlkKEEpIHx8IHZpc1tBLmZdW0Euc10gPT0gY250KSBjb250aW51ZTsKCQkJaWYgKHN0W0EuZl1bQS5zXS5mICE9IGNudCkgc3RbQS5mXVtBLnNdID0ge2NudCwwfTsKCQkJc3RbQS5mXVtBLnNdLnMgfD0gMTw8aTsKCQkJaWYgKG14W3N0W0EuZl1bQS5zXS5zXSA+PSBVW0EuZl1bQS5zXSkgewoJCQkJbnVtICsrOyB2aXNbQS5mXVtBLnNdID0gY250OyBxLnB1c2goQSk7CgkJCQlpZiAoZ2V0Q29tcChBKSAhPSBjb21wW3guZl1beC5zXS1NT0QpIHJldHVybiB7Z2V0Q29tcChBKSxudW19OwoJCQl9CgkJfQoJfQoJcmV0dXJuIHtNT0QsbnVtfTsKfQoKdm9pZCBqb2luKGludCBhLCBpbnQgYikgewoJYSA9IGdldChhKSwgYiA9IGdldChiKTsgCglpZiAoYSA9PSBiKSByZXR1cm47Cglhc3NlcnQoYSAhPSAtMSk7CglpZiAoYiA9PSAtMSkgewoJCXRyYXYodCxyY29tcFthXSkgY29tcFt0LmZdW3Quc10gPSAtMTsgCgkJcGFyW2FdID0gYjsgcmNvbXBbYV0uY2xlYXIoKTsKCQlyZXR1cm47Cgl9CglpZiAoc3oocmNvbXBbYV0pID4gc3oocmNvbXBbYl0pKSB7CgkJcGkgQSA9IHJjb21wW2FdLmJhY2soKTsgY29tcFtBLmZdW0Euc10gPSBhOwoJCXRyYXYodCxyY29tcFtiXSkgewoJCQljb21wW3QuZl1bdC5zXSA9IGE7CgkJCXJjb21wW2FdLnBiKHQpOwoJCX0KCQlBID0gcmNvbXBbYV0uYmFjaygpOyBjb21wW0EuZl1bQS5zXSA9IGErTU9EOwoJCXBhcltiXSA9IGE7IHJjb21wW2JdLmNsZWFyKCk7Cgl9IGVsc2UgewoJCWludCBpbmQgPSBzeihyY29tcFtiXSktMTsKCQl0cmF2KHQscmNvbXBbYV0pIHsKCQkJY29tcFt0LmZdW3Quc10gPSBiOwoJCQlyY29tcFtiXS5wYih0KTsKCQl9CgkJc3dhcChyY29tcFtiXVtpbmRdLHJjb21wW2JdLmJhY2soKSk7CgkJcGFyW2FdID0gYjsgcmNvbXBbYV0uY2xlYXIoKTsKCX0KfQoKaW50IG1haW4oKSB7Cglpbml0KCk7CiAgICBGMFIoaSwxMDApIHsKICAgIAl2cGkgZWQ7CiAgICAJRjBSKGksUikgRjBSKGosQykgaWYgKGNvbXBbaV1bal0gPj0gTU9EKSB7IC8vIHNwZWNpYWwgY2VsbAogICAgCQlpbnQgYyA9IGNvbXBbaV1bal0tTU9EOwogICAgCQlwaSB4ID0gYmZzKHtpLGp9KTsKICAgIAkJaWYgKHguZiA9PSBNT0QpIHsgLy8gbm8gbmV3IGNvbXBvbmVudCByZWFjaGVkLCB1cGRhdGUgYW5zd2VyCiAgICAJCQlpZiAoYW5zLmYgPiB4LnMpIGFucyA9IHt4LnMsMH07CiAgICAJCQlpZiAoYW5zLmYgPT0geC5zKSBhbnMucyArPSB4LnM7CiAgICAJCQllZC5wYih7YywtMX0pOwogICAgCQl9IGVsc2UgaWYgKHguZiA9PSAtMSkgewogICAgCQkJZWQucGIoe2MsLTF9KTsKICAgIAkJfSBlbHNlIGVkLnBiKHtjLHguZn0pOwogICAgCX0KICAgIAlpZiAoIXN6KGVkKSkgYnJlYWs7CiAgICAJdHJhdih0LGVkKSB7CiAgICAJCWpvaW4odC5mLHQucyk7IC8vIG1lcmdlIGNvbXBvbmVudHMKICAgIAl9CiAgICB9CiAgICBwcyhhbnMuZixhbnMucyk7Cn0KCi8qIHN0dWZmIHlvdSBzaG91bGQgbG9vayBmb3IKICAgICogaW50IG92ZXJmbG93LCBhcnJheSBib3VuZHMKICAgICogc3BlY2lhbCBjYXNlcyAobj0xPyksIHNldCB0bGUKICAgICogZG8gc210aCBpbnN0ZWFkIG9mIG5vdGhpbmcgYW5kIHN0YXkgb3JnYW5pemVkCiov