// #pragma GCC optimize "O3,unroll-loops,omit-frame-pointer,inline"

#include <bits/stdc++.h>
using namespace std;

/* useful defines with short names */
#define st first
#define nd second
#define pb push_back
#define pp pop_back
#define all(x) (x).begin(), (x).end()
#define lb(a, b, c) lower_bound(a, b, c)
#define ub(a, b, c) upper_bound(a, b, c)
#define forn(i, n) for (int i = 0; i < (n); ++i)
#define ford(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define len(x) (int)(x).size()
#define low(x) ((x) & (-(x))) // lowest bit in number
#define ispow(x) low(x) == (x) // is power of two
#define subm(m, mask) for (int m = ((mask) - 1) & (mask); m; m = (m - 1) & (mask)) // iterate through submasks
#define pct(x) __builtin_popcount(x) // number of set bits in x
#define bits(x) (31 - __builtin_clz(x)) // floor(log2(x))

/* useful typedefs with short names */
typedef long long	ll;
typedef double 	db;
typedef long double ldb;
typedef complex<db> cd;
typedef string      str;

typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef pair<db, db>	pdb;
typedef pair<ldb, ldb>	pldb;
typedef pair<int, ll>	pil;
typedef pair<ll, int>	pli;

template<typename T = int>
using vv = vector<T>;

template<typename T1 = int, typename T2 = int>
using umap = unordered_map<T1, T2>;

template<typename T = int>
using uset = unordered_set<T>;

typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<str>      vs;
typedef vector<char>	vc;
typedef vector<bool>     vb;
typedef vector<db>		vdb;
typedef vector<ldb>		vldb;
typedef vector<pii>		vpii;
typedef vector<pll>		vpll;
typedef vector<pdb>		vpdb;
typedef vector<pldb>	vpldb;
typedef vector<pil>		vpil;
typedef vector<pli>		vpli;
typedef vector<vi> 		vvi;
typedef vector<vl>       vvl;

/* pair<T1, T2> operators: +, -, +=, -=, *, *=, -(unary) */
template<typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2>& a, const pair<T1, T2>& b);
template<typename T1, typename T2>
pair<T1, T2>& operator+=(pair<T1, T2>& a, const pair<T1, T2>& b);
template<typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2>& p);
template<typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2>& a, const pair<T1, T2>& b);
template<typename T1, typename T2>
pair<T1, T2>& operator-=(pair<T1, T2>& a, const pair<T1, T2>& b);
template<typename T1, typename T2, typename T3>
pair<T1, T2> operator*(const pair<T1, T2>& p, T3 mult);
template<typename T1, typename T2, typename T3>
pair<T1, T2> operator*(T3 mult, const pair<T1, T2>& p);

/* modular arithmetic class implementation */
template<int MOD=1'000'000'007>
struct modular
{
    int val;
 
    modular(ll v = 0) {
        if (v < 0) v = v % MOD + MOD;
        if (v >= MOD) v %= MOD;
        val = int(v);
    }
    modular(uint64_t v) {
        if (v >= MOD) v %= MOD;
        val = int(v);
    }
 
    modular(int v) : modular(ll(v)) {}
    modular(unsigned v) : modular(uint64_t(v)) {}
 
    static int inv_mod(int a, int m = MOD) {
        // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
        int g = m, r = a, x = 0, y = 1;
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        }
        return x < 0 ? x + m : x;
    }
 
    explicit operator int() const { return val; }
    explicit operator unsigned() const { return val; }
    explicit operator ll() const { return val; }
    explicit operator uint64_t() const { return val; }
    explicit operator double() const { return val; }
    explicit operator long double() const { return val; }
 
    modular& operator+=(const modular &other) {
        val -= MOD - other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    modular& operator-=(const modular &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
        return unsigned(x % m);
#endif
        // Optimized mod for Codeforces 32-bit machines.
        // x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
        unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
        unsigned quot, rem;
        asm("divl %4\n"
            : "=a" (quot), "=d" (rem)
            : "d" (x_high), "a" (x_low), "r" (m));
        return rem;
    }
 
    modular& operator*=(const modular &other) {
        val = fast_mod(uint64_t(val) * other.val);
        return *this;
    }
 
    modular& operator/=(const modular &other) {
        return *this *= other.inv();
    }
 
    friend modular operator+(const modular &a, const modular &b) { return modular(a) += b; }
    friend modular operator-(const modular &a, const modular &b) { return modular(a) -= b; }
    friend modular operator*(const modular &a, const modular &b) { return modular(a) *= b; }
    friend modular operator/(const modular &a, const modular &b) { return modular(a) /= b; }
 
    modular& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }
 
    modular& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }
 
    modular operator++(int) { modular before = *this; ++*this; return before; }
    modular operator--(int) { modular before = *this; --*this; return before; }
 
    modular operator-() const {
        return val == 0 ? 0 : MOD - 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.val != b.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.val > b.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.val >= b.val; }
 
    modular inv() const {
        return inv_mod(val);
    }
 
    modular pow(int64_t p) const {
        if (p < 0)
            return inv().pow(-p);
        modular a = *this, result = 1;
        while (p > 0) {
            if (p & 1)
                result *= a;
            p >>= 1;
            if (p > 0)
                a *= a;
        }
        return result;
    }
 
    friend ostream& operator<<(ostream &os, const modular &m) {
        return os << m.val;
    }
};
 
/* scanf with template */
template<typename T> T scanf_t();

/* scanf template specializations */
template<>  int            scanf_t();
template<>  ll             scanf_t();
template<>  db             scanf_t();
template<>  ldb            scanf_t();
template<>  char           scanf_t();
template<>  float          scanf_t();
template<>  str 	       scanf_t();
str         scanf_t(int);  

/* short names for scanf template specializations */
int     (*si)()     =  scanf_t<int>;
ll      (*sl)()     =  scanf_t<ll>;
db      (*sdb)()    =  scanf_t<db>;
ldb     (*sldb)()   =  scanf_t<ldb>;
char    (*sc)()     =  scanf_t<char>;
float   (*sf)()     =  scanf_t<float>;
str 	   (*ss)()     =  scanf_t<str>;

/* printf template functions */
template<typename T> void printf_t(const T&, char='\n', FILE* = stdout);
template<typename T> void printf_t(const T*, char='\n', FILE* = stdout);
template<typename T> void printf_t(T*, char='\n', FILE* = stdout);
template<typename T1, typename T2> void printf_t(const pair<T1, T2>&, char='\n', FILE* = stdout);
template<typename T, typename Alloc, template<typename, typename> class Container>
void printf_t(const Container<T, Alloc>&, char='\n', FILE* = stdout);

/* varadic print that uses printf */
void print();
template<typename T> void _print(char endl, const T&);
template<typename T, typename... Args> void _print(char endl, const T&, const Args&...);
template<typename T> void _print(char endl, T*, T*);
template<typename T> void _print(char endl, T*, int);
template<typename... Args> void print(const Args&...);

/* variadic print without newline at the end */
template<typename... Args> void prt(const Args&...);
template<typename T> void prt(T*, T*);
template<typename T> void prt(T*, int);

/* variadic print to stderr that uses printf */
template<typename T>
void __dbg(const char*, const T&);
template<typename T, typename... Args>
void __dbg(const char*, const T&, const Args&...);
template<typename... Args>
void _dbg(const char*, const Args&...);
template<typename T>
void _dbg(const char*, T*, T*, char='\n', char=' ');
template<typename T>
void _dbg(const char*, T*, int, char='\n', char=' ');

/* when debugging to stderr, grab also names of variables */
#ifdef LOCAL
	#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
	#define dbg(...)
#endif

/* read to array from standard input with scanf */
template<typename T> void in(T*, int);
/* read to standard C++ container with scanf and push_back */
template<typename T, typename Alloc, template<typename, typename> class Container>
void sv(Container<T, Alloc>&, int);
template<typename T, typename Alloc>
void sv(vector<T, Alloc>&, int);

/* write an array to standard output */
template<typename It> void out(It, It, char='\n', char=' ', FILE* = stdout);
template<typename It> void out(It, int, char='\n', char=' ', FILE* = stdout);
/* write standard C++ container to standard output */
template<typename Container> void pv(const Container&, char='\n', char=' ', FILE* = stdout);

/* debug functions */
template<typename T>
void print_bits(T x, int=0);

/* useful variables, functions, definitions*/
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define shuffle(a, b) shuffle(a, b, rng)
template<typename T> T rand(T a, T b);
template<typename T> T rand(T n);
template<typename It> It uniq(It begin, It end);
template<typename T> void uniq(vv<T>& v);

/* short names for printf template specializations */
void pi(const int&, char='\n');
void pl(const ll&, char='\n');
void pd(const db&, char='\n');
void pld(const ldb&, char='\n');
void pf(const float&, char='\n');
void pc(const char&, char='\n');
void ps(const str&, char='\n');

/* geometry */
template<typename T1, typename T2>
ll cross(const pair<T1, T2>& p1, const pair<T1, T2>& p2);
template<typename T1, typename T2>
ll dot(const pair<T1, T2>& p1, const pair<T1, T2>& p2);
template<typename T1, typename T2>
ldb vlen(const pair<T1, T2>& v);

/* useful, general purpose algorithms */
ll russian(ll, ll, ll);
ll fastpow(ll, ll, ll);
ll slowpow(ll, ll, ll);
ll extgcd(ll, ll, ll&, ll&);
ll _gcd(ll, ll);
ll _lcm(ll, ll);
ll _inv(ll, ll);

/* useful constants */
const  int  INF   =  1e9;
const  ll   LINF  =  1e18;
const  ll   M     =  1e9 + 7;
// const  ll   M 	   =  998244353LL; 
const  ldb  PI    =  acos(-1);
const  ldb  PI_2  =  PI / 2;

typedef modular<M> mod;

#define EMPTY ' '
#define SUN '*'
#define HOUSE '^'
#define CHUP '!'
#define LSLOP '/'
#define RSLOP '\\'
#define BIRD 'v'
#define DRAKE 'D'
#define GRILL 'G'

const char objects[] = {
    SUN, HOUSE, CHUP, LSLOP,
    RSLOP, BIRD, DRAKE, GRILL
};

const int N = 50 + 7;
const pii lines[] = {
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0},
    {1, 1},
    {-1, -1},
    {-1, 1},
    {1, -1}
};
const pii rows[] = {
    {0, 1},
    {0, -1}
};
const pii edges[] = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};
const pii knight[] = {
    {2, 1},
    {2, -1},
    {-2, 1},
    {-2, -1},
    {1, 2},
    {1, -2},
    {-1, 2},
    {-1, -2}
};
char t[N][N];
int vis[N][N];
int n;

bool inbounds(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

bool isnonempty(int x, int y) {
    assert(inbounds(x, y));
    return t[x][y] != EMPTY;
}

bool isempty(int x, int y) {
    assert(inbounds(x, y));
    return t[x][y] == EMPTY;
}

bool issun(int x, int y) {
    assert(inbounds(x, y));
    return t[x][y] == SUN;
}

bool isbird(int x, int y) {
    assert(inbounds(x, y));
    return t[x][y] == BIRD || t[x][y] == DRAKE;
}

bool ishouse(int x, int y) {
    assert(inbounds(x, y));
    return t[x][y] == HOUSE;
}

bool isanimal(int x, int y) {
    assert(inbounds(x, y));
    return t[x][y] == CHUP || t[x][y] == BIRD || t[x][y] == DRAKE;
}

bool isborder(int x, int y) {
    assert(inbounds(x, y));
    return x == 0 || y == 0 || x == n - 1 || y == n - 1;
}

bool ischup(int x, int y) {
    assert(inbounds(x, y));
    return t[x][y] == CHUP;
}

bool ispeak(int x, int y) {
    assert(inbounds(x, y) && inbounds(x, y + 1));
    return t[x][y] == LSLOP && t[x][y + 1] == RSLOP;
}

bool isdrake(int x, int y) {
    assert(inbounds(x, y));
    return t[x][y] == DRAKE;
}

bool isgrill(int x, int y) {
      assert(inbounds(x, y));
    return t[x][y] == GRILL;
}

int count_this(char obj) {
    int cnt = 0;
    forn (i, n) {
        forn (j, n) {
            if (t[i][j] == obj) {
                ++cnt;
            }
        }
    }
    return cnt;
}

ll suns_rule() {
    dbg("suns_rule");
    ll value = 0;
    ll ill_c = 0;
    forn (i, n) {
        forn (j, n) {
            if (isnonempty(i, j) && !issun(i, j)) {
                bool ill = false;
                for (auto [lx, ly] : lines) {
                    int x = i + lx;
                    int y = j + ly;
                    while (inbounds(x, y) && isempty(x, y)) {
                        x += lx;
                        y += ly;
                    }
                    if (inbounds(x, y) && issun(x, y)) {
                        ill = true;
                        break;
                    }
                }
                if (ill)
                    ill_c++;
            }
        }
    }
    dbg(value);
    value += ill_c * 100;
    dbg(ill_c);
    return value;
}

void reset() {
    forn (i, n) {
        forn (j, n) {
            vis[i][j] = 0;
        }
    }
}

ll biggest_bird_and_flock_per_rule() {
    ll value = 0;
    vpii cells;
    queue<pii> q;
    int flock = 0;
    reset();
    forn (i, n) {
        forn (j, n) {
            if (!vis[i][j] && isbird(i, j)) {
                dbg("FLOCK");
                ++flock;
                while (!q.empty())
                    q.pop();
                cells.clear();
                q.push({i, j});
                vis[i][j] = flock;
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    cells.push_back({x, y});
                    for (auto [dx, dy] : edges) {
                        int nx = x + dx;
                        int ny = y + dy;
                        if (!inbounds(nx, ny) || !isbird(nx, ny) || vis[nx][ny] == flock)
                            continue;
                        vis[nx][ny] = flock;
                        q.push({nx, ny});
                    }
                }
                for (auto [x, y] : cells) {
                    assert(vis[x][y] == flock);
                    for (auto [dx, dy] : edges) {
                        int nx = x + dx;
                        int ny = y + dy;
                        if (inbounds(nx, ny)) {
                            if (isbird(nx, ny)) {
                                assert(vis[nx][ny] == flock);
                            }
                            else {
                                assert(vis[nx][ny] == 0);
                            }
                        }
                    }
                }
                ll width = 0;
                for (auto [x, y] : cells) {
                    for (auto [dx, dy] : rows) {
                        int nx = x, ny = y;
                        ll l = 0;
                        while (inbounds(nx, ny) && vis[nx][ny] == flock) {
                            nx += dx;
                            ny += dy;
                            ++l;
                        }
                        width = max(width, l);
                    }
                }
                value += width * 500;
                dbg(width);
                ll per = 0;
                for (auto [x, y] : cells) {
                    for (auto [dx, dy] : edges) {
                        int nx = x + dx;
                        int ny = y + dy;
                        if (!inbounds(nx, ny) || !isbird(nx, ny))
                            ++per;
                    }
                }
                value += per * 60;
                dbg(per);
            }
        }
    }
    dbg(value);
    return value;
}

ll house_view_up_rule() {
    dbg("house_view_up");
    ll empty_c = 0;
    ll value = 0;
    forn (i, n) {
        forn (j, n) {
            if (ishouse(i, j)) {
                int x = i - 1;
                int y = j;
                while (inbounds(x, y) && isempty(x, y))
                    --x, ++empty_c;
            }
        }
    }
    dbg(empty_c);
    value += empty_c * 10;
    dbg(value);
    return value;
}

ll blocks3x3_rule() {
    ll value = 0;
    set<vc> s;
    forn (i, n - 2) {
        forn (j, n - 2) {
            vc v;
            forn (a, 3) {
                forn (b, 3) {
                    v.push_back(t[i + a][j + b]);
                }
            }
            s.insert(v);
        }
    }
    value += s.size();
    return value;
}

ll animal1_rule() {
    ll value = 0;
    dbg("animal1");
    ll edges_c = 0;
    forn (i, n) {
        forn (j, n) {
            if (isanimal(i, j)) {
                for (auto [dx, dy] : edges) {
                    int nx = i + dx;
                    int ny = j + dy;
                    if (inbounds(nx, ny) && isempty(nx, ny)) {
                        ++edges_c;
                    }
                }
            }
        }
    }
    dbg(edges_c);
    value += edges_c * 15;
    dbg(value);
    return value;
}

ll freedom_rule() {
    ll value = 0;
    dbg("freedom");
    reset();
    queue<pii> q;
    forn (i, n) {
        forn (j, n) {
            if (isempty(i, j) && isborder(i, j)) {
                q.push({i, j});
                vis[i][j] = 1;
            }
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (auto [dx, dy] : edges) {
            int nx = x + dx;
            int ny = y + dy;
            if (inbounds(nx, ny) && isempty(nx, ny) && !vis[nx][ny]) {
                vis[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
    ll freedom_c = 0;
    forn (i, n) {
        forn (j, n) {
            if (isnonempty(i, j)) {
                bool freedom = isborder(i, j);
                for (auto [dx, dy] : edges) {
                    int nx = i + dx;
                    int ny = j + dy;
                    if (inbounds(nx, ny) && vis[nx][ny]) {
                        freedom = true;
                        break;
                    }
                }
                if (freedom)
                    freedom_c++;
            }
        }
    }
    dbg(freedom_c);
    value += freedom_c * 7;
    dbg(value);
    return value;
}

ll chup_rule() {
    dbg("chup");
    ll value = 0;
    ll bird_c = 0;
    forn (i, n) {
        forn (j, n) {
            if (isbird(i, j)) {
                bool good = false;
                for (auto [dx, dy] : knight) {
                    int nx = i + dx;
                    int ny = j + dy;
                    if (inbounds(nx, ny) && ischup(nx, ny)) {
                        good = true;
                        break;
                    }
                }
                if (good)
                    ++bird_c;
            }
        }
    }
    dbg(bird_c);
    value += bird_c * 200;
    dbg(value);
    return value;
}

ll peaks_rule() {
    dbg("peaks");
    ll value = 0;
    vpii peaks;
    forn (i, n) {
        forn (j, n - 1) {
            if (ispeak(i, j)) {
                peaks.emplace_back(i, j);
            }
        }
    }
    for (auto p1 : peaks) {
        ll max_d = 0;
        for (auto p2 : peaks) {
            max_d = max(max_d, (ll)abs(p1.st - p2.st) + abs(p1.nd - p2.nd));
        }
        dbg(max_d);
        value += max_d * 50;
    }
    dbg(value);
    return value;
}

ll drake_grill_rule() {
    ll value = 0;
    ll drake_c = 0;
    dbg("drake");
    forn (i, n) {
        forn (j, n) {
            if (isdrake(i, j)) {
                bool good = false;
                for (auto [dx, dy] : edges) {
                    int nx = i + dx;
                    int ny = j + dy;
                    if (inbounds(nx, ny) && isgrill(nx ,ny)) {
                        good = true;
                        break;
                    }
                }
                if (good)
                    drake_c++;
            }
        }
    }
    dbg(drake_c);
    value += drake_c * 500;
    dbg(value);
    return value;
}

ll minimum_freq_rule() {
    ll value = 0;
    dbg("min_freq");
    ll freq = INF;
    for (auto obj : objects) {
        ll tmp = count_this(obj);
        if (tmp) {
            freq = min(freq, tmp);
        }
    }
    if (freq == INF)
        freq = 0;
    for (auto obj : objects) {
        ll f = count_this(obj);
        if (f == freq) {
            dbg(obj);
            value += freq * 10;
        }
    }
    dbg(freq);
    dbg(value);
    return value;
}

ll empty_fields_rule() {
    ll value = 0;
    dbg("empty_fields");
    ll empty_c = count_this(EMPTY);
    value += empty_c * 1;
    dbg(empty_c);
    dbg(value);
    return value;
}

ll animal2_rule() {
    ll value = 0;
    dbg("animal2");
    ll a = count_this(CHUP);
    ll b = count_this(BIRD);
    ll c = count_this(DRAKE);
    dbg(a, b, c);
    value += a * b * c;
    dbg(value);
    return value;
}

ll house_view_down_rule() {
    ll value = 0;
    ll empty_c = 0;
    dbg("house_view_down");
    forn (i, n) {
        forn (j, n) {
            if (ishouse(i, j)) {
                int x = i - 1;
                int y = j;
                while (inbounds(x, y) && isempty(x, y))
                    --x, ++empty_c;
            }
        }
    }
    dbg(empty_c);
    value += empty_c * 5;
    dbg(value);
    return value;
}

ll grill_drake_rule() {
    ll value = 0;
    ll grill_c = 0;
    dbg("grill_drake");
    forn (i, n) {
        forn (j, n) {
            if (isgrill(i, j)) {
                bool good = false;
                for (auto [dx, dy] : edges) {
                    int nx = i + dx;
                    int ny = j + dy;
                    if (inbounds(nx, ny) && isdrake(nx, ny)) {
                        good = true;
                        break;
                    }
                }
                if (good)
                    grill_c++;
            }
        }
    }
    dbg(grill_c);
    value += grill_c * 50;
    dbg(value);
    return value;
}

ll house_and_grills_rule() {
    ll value = 0;
    dbg("house_and_grills");
    ll a = count_this(HOUSE);
    ll b = count_this(GRILL);
    dbg(a, b);
    dbg(min(a, b));
    value += 3 * min(a, b);
    dbg(value);
    return value;
}

ll solve() {
    n = si();
    getchar();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            t[i][j] = getchar();
            // printf("%c", t[i][j]);
        }
        getchar();
        // puts("");
    }

    ll value = 0;
    value += suns_rule();
    value += biggest_bird_and_flock_per_rule();
    value += house_view_up_rule();
    value += blocks3x3_rule();
    value += animal1_rule();
    value += freedom_rule();
    value += chup_rule();
    value += peaks_rule();
    value += drake_grill_rule();
    value += minimum_freq_rule();
    value += empty_fields_rule();
    value += animal2_rule();
    value += house_view_down_rule();
    value += grill_drake_rule();
    value += house_and_grills_rule();
    return value;
}

int main()
{
    // int t = si();
	int t = 1;
	while (t--) {
        print(solve());
    }

	return 0;
}

/* scanf template specilizations */
template<> int scanf_t() { int x; scanf("%d", &x); return x; }
template<> db scanf_t() { db x; scanf("%lf", &x); return x; }
template<> ll scanf_t() { ll x; scanf("%lld", &x); return x; }
template<> ldb scanf_t() { ldb x; scanf("%Lf", &x); return x; }
template<> char scanf_t() { char x; scanf(" %c", &x); return x; }
template<> float scanf_t() { float x; scanf("%f", &x); return x; }

/* printf template specilizations */
template<> void printf_t(const int& x, char end, FILE* out) { fprintf(out, "%d%c", x, end); }
template<> void printf_t(const ll& x, char end, FILE* out) { fprintf(out, "%lld%c", x, end); }
template<> void printf_t(const db& x, char end, FILE* out) { fprintf(out, "%.8lf%c", x, end); }
template<> void printf_t(const ldb& x, char end, FILE* out) { fprintf(out, "%.10Lf%c", x, end); }
template<> void printf_t(const float& x, char end, FILE* out) { fprintf(out, "%f%c", x, end); }
template<> void printf_t(const char& x, char end, FILE* out) { fprintf(out, "%c%c", x, end); }
template<> void printf_t(const str& x, char end, FILE* out) { fprintf(out, "%s%c", x.c_str(), end); }
template<> void printf_t(const char* x, char end, FILE* out) { fprintf(out, "%s%c", x, end); }
template<> void printf_t(char* x, char end, FILE* out) { fprintf(out, "%s%c", x, end); }
template<> void printf_t(const mod& x, char end, FILE* out) { printf_t(x.val, end, out); }
template<> void printf_t(const uint64_t& x, char end, FILE* out) { fprintf(out, "%lu%c", x, end); }
template<> void printf_t(const uint32_t& x, char end, FILE* out) { fprintf(out, "%u%c", x, end); }
template<> void printf_t(const bool& x, char end, FILE* out) { fprintf(out, "%d%c", x, end); }
template<> void printf_t(const long& x, char end, FILE* out) { fprintf(out, "%ld%c", x, end); }
template<typename T1, typename T2> void printf_t(const pair<T1, T2>& x, char end, FILE* out) { printf_t(x.st, ' ', out); printf_t(x.nd, end, out); }
template<typename T, typename Alloc, template<typename, typename> class Container>
void printf_t(const Container<T, Alloc>& v, char end, FILE* out) { pv(v, end, ' ', out); }

/* scanf str of unknown length */
template<>
str scanf_t()
{
	int size = 8;
	char* s = (char*)malloc(size * sizeof(char));
	char c;
	while (isspace(c = getchar()));
	*s = c;
	int i = 1;
	while (!isspace(c = getchar()))
	{
		s[i++] = c;
		if (i == size)
			s = (char*)realloc(s, size *= 2);
	}
	s[i] = '\0';
	str res(s);
	free(s);
	return res;
}

/* make print() possible */
void print() { printf("\n"); }

/* variadic print base case */
template<typename T> void _print(char endl, const T& last) { printf_t(last, endl); }

/* variadic print */
template<typename T, typename... Args>
void _print(char endl, const T& first, const Args&... rest)
{
	printf_t(first, ' ');
	_print(endl, rest...);
}

/* print array from begin iterator to end iterator */
template<typename T>
void _print(char endl, T* begin, T* end) { out(begin, end, endl); }

/* print n elements from of array starting from begin iterator */
template<typename T>
void _print(char endl, T* begin, int n) { out(begin, begin + n, endl); }

/* variadic print with newline at the end */
template<typename... Args>
void print(const Args&... args) { _print('\n', args...); }

/* variadic print with no newline at the end */
template<typename... Args>
void prt(const Args&... args) { _print(' ', args...); }

/* analogous to print(T*, T*) */
template<typename T>
void prt(T* begin, T* end) { _print(' ', begin, end); }

/* analogous to print(T*, int) */
template<typename T>
void prt(T* begin, int n) { _print(' ', begin, n); }

/* variadic __dbg base case */
template<typename T>
void __dbg(const char* s, const T& x)
{
	fprintf(stderr, "%s = ", s);
	printf_t(x, ' ', stderr);
}

/* variadic __dbg */
template<typename T, typename... Args>
void __dbg(const char* s, const T& x, const Args&... rest)
{
	int bracket = 0;
	char c;
	while ((c = *s) != ',' || bracket)
	{
		fprintf(stderr, "%c", *s++);
		switch (c)
		{
			case '(':
			case '{':
			case '[':
				++bracket;
				break;
			case ')':
			case '}':
			case ']':
				--bracket;
		}
	}
	fprintf(stderr, " = ");
	printf_t(x, '\0', stderr);
	fprintf(stderr, ",");
	__dbg(s + 1, rest...);
}

/* variadic _dbg - print braces around */
template<typename... Args>
void _dbg(const char* s, const Args&... rest)
{
	fprintf(stderr, "[ ");
	__dbg(s, rest...);
	fprintf(stderr, "]\n");
}

/* _dbg array from begin to end */
template<typename T>
void _dbg(const char* s, T* begin, T* end, char endl, char sep)
{
	fprintf(stderr, "[ ");
	while (*s != ',')
		fprintf(stderr, "%c", *s++);
	fprintf(stderr, " = ");
	out(begin, end, ' ', sep, stderr);
	fprintf(stderr, "]%c", endl);
}

/* _dbg n elements of array starting from begin */
template<typename T>
void _dbg(const char* s, T* begin, int n, char endl, char sep)
{
	_dbg(s, begin, begin + n, endl, sep);
}

/* scanf n variables of type T */
template<typename T>
void in(T* begin, int n)
{
	while (n--)
		*begin++ = scanf_t<T>();
}

/* scanf n variables of type T to standard C++ container and push them back */
template<typename T, typename Alloc, template<typename, typename> class Container>
void sv(Container<T, Alloc>& v, int n)
{
	auto it = std::back_inserter(v);
	while (n--)
		*it = scanf_t<T>();
}

/* little optimization */
template<typename T, typename Alloc>
void sv(vector<T, Alloc>& v, int n)
{
	v.reserve(n);
	auto it = std::back_inserter(v);
	while (n--)
		*it = scanf_t<T>();
}

/* printf array to standard output */
template<typename It>
void out(It begin, It end, char endl, char sep, FILE* outs)
{
	if (begin == end)
	{
		fprintf(outs, "%c", endl);
		return;
	}	
	while (next(begin) != end)
		printf_t(*begin++, sep, outs);
	printf_t(*begin, endl, outs);
}

/* printf array to standard output */
template<typename It>
void out(It begin, int n, char endl, char sep, FILE* outs) { out(begin, begin + n, endl, sep, outs); }

/* printf standard C++ container to standard output */
template<typename Container>
void pv(const Container& v, char end, char sep, FILE* outs) { out(all(v), end, sep, outs); }

/* implementation short named functions for template specializations */
void  pi(const   int&     x, char end)  {  printf_t(x, end);  }
void  pl(const   ll&      x, char end)  {  printf_t(x, end);  }
void  pd(const   db&      x, char end)  {  printf_t(x, end);  }
void  pld(const  ldb&     x, char end)  {  printf_t(x, end);  }
void  pf(const   float&   x, char end)  {  printf_t(x, end);  }
void  pc(const   char&    x, char end)  {  printf_t(x, end);  }
void  ps(const   str&  x, char end)     {  printf_t(x, end);  }

/* pair<T1, T2> operators: +, -, +=, -=, *, *=, -(unary) */
template<typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2>& a, const pair<T1, T2>& b) { return { a.st + b.st, a.nd + b.nd }; }
template<typename T1, typename T2>
pair<T1, T2>& operator+=(pair<T1, T2>& a, const pair<T1, T2>& b) { a.st += b.st; a.nd += b.nd; return a; }
template<typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2>& p) { return { -p.st, -p.nd }; }
template<typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2>& a, const pair<T1, T2>& b) { return { a.st - b.st, a.nd - b.nd }; }
template<typename T1, typename T2>
pair<T1, T2>& operator-=(pair<T1, T2>& a, const pair<T1, T2>& b) { a.st -= b.st; a.nd -= b.nd; return a; }
template<typename T1, typename T2, typename T3>
pair<T1, T2> operator*(const pair<T1, T2>& p, T3 mult) { return {p.st * mult, p.nd * mult}; }
template<typename T1, typename T2, typename T3>
pair<T1, T2> operator*(T3 mult, const pair<T1, T2>& p) { return {p.st * mult, p.nd * mult}; }

/* geometry functions */
template<typename T1, typename T2>
ll cross(const pair<T1, T2>& p1, const pair<T1, T2>& p2) { return p1.st * p2.nd - p1.nd * p2.st; }
template<typename T1, typename T2>
ll dot(const pair<T1, T2>& p1, const pair<T1, T2>& p2) { return p1.st * p2.st + p1.nd * p2.nd; }
template<typename T1, typename T2>
ldb vlen(const pair<T1, T2>& v) { return sqrtl(dot(v, v)); }

/* russian peasants algorithm */
ll russian(ll a, ll k, ll m)
{
	ll res = 0LL;
	while (k)
	{
		if (k & 1LL)
			res = (res + a) % m;
		a = (a + a) % m;
		k >>= 1;
	}
	return res;
}

/* fast power - a^k % m */
ll fastpow(ll a, ll k, ll m)
{
	ll res = 1LL;
	while (k)
	{
		if (k & 1LL)
			res = (res * a) % m;
		a = (a * a) % m;
		k >>= 1;
	}
	return res;
}

/* fast power with russian peasants algorithm */
ll slowpow(ll a, ll k, ll m)
{
	ll res = 1LL;
	while (k)
	{
		if (k & 1LL)
			res = russian(res, a, m);
		a = russian(a, a, m);
		k >>= 1;	
	}
	return res;
}

/* greatest common divisor of a and b */
ll _gcd(ll a, ll b)
{
	while (b)
		swap(a %= b, b);
	return a;
}

/* least common multiple of a and b */
ll _lcm(ll a, ll b)
{
	return a / _gcd(a, b) * b;
}

/* calculate inverse of a modulo */
ll _inv(ll a, ll p)
{
	return fastpow(a, p - 2, p);
}

/* extended Eucilean algorithm implementation - calculate a * k + b * l = GCD(a, b) */
ll extgcd(ll a, ll b, ll& k, ll& l)
{
	if (b == 0)
	{
		k = 1; l = 0;
		return a;
	}
	ll res = extgcd(b, a % b, l, k);
	l -= a / b * k;
	return res;
}

/* print bits of number x */
template<typename T>
void print_bits(T x, int force_len)
{
	assert(0 <= force_len && force_len <= 64);
	static char s[64];
	int i = 63;
	if (force_len)
		while (force_len--)
			s[i--] = '0' + (x & 1),
			x >>= 1;
	else
		while (x)
			s[i--] = '0' + (x & 1),
			x >>= 1;
	printf("%s\n", s + i + 1);
}

/* random number between a and b (integer or float depending on type T) */
template<typename T>
T rand(T a, T b)
{
	using dist = conditional_t<
		is_integral<T>::value,
		uniform_int_distribution<T>,
		uniform_real_distribution<T>
	>;
	return dist(a, b)(rng);
}

/* random number between 0 and n-1 */
template<typename T>
T rand(T n)
{
	static_assert(is_integral<T>::value, "Only integral type supported!");
	return uniform_int_distribution<T>(0, n - 1)(rng);
}

/* "delete" repeated occurences */
template<typename It>
It uniq(It begin, It end)
{
	sort(begin, end);
	return unique(begin, end);
}

/* delete non-unique elements from vector */
template<typename T>
void uniq(vv<T>& v) { v.erase(uniq(all(v)), v.end()); }