include<bits/stdc++.h>

include <algorithm>

include <bitset>

include <complex>

include <deque>

include <exception>

include <fstream>

include <functional>

include <iomanip>

include <ios>

include <iosfwd>

include <iostream>

include <istream>

include <iterator>

include <limits>

include <list>

include <locale>

include <map>

include <memory>

include <new>

include <numeric>

include <ostream>

include <queue>

include <set>

include <unordered_set>

include <sstream>

include <stack>

include <stdexcept>

include <streambuf>

include <string>

include <typeinfo>

include <utility>

include <valarray>

include <vector>

include <cstring>

include <unordered_map>

include <cmath>

include <cassert>

/*
+---+ +---------------+ +---------------+ +---------------+ +-----------+
¦Esc¦ ¦ F1¦ F2¦ F3¦ F4¦ ¦ F5¦ F6¦ F7¦ F8¦ ¦ F9¦F10¦F11¦F12¦ ¦P/S¦S L¦P/B¦ ++ ++ ++
+---+ +---------------+ +---------------+ +---------------+ +-----------+ ++ ++ ++
+-----------------------------------------------------------+ +-----------+ +---------------+
¦~ `¦! 1¦@ 2¦# 3¦$ 4¦% 5¦^ 6¦& 7¦* 8¦( 9¦) 0¦_ -¦+ =¦ BacSp ¦ ¦Ins¦Hom¦PUp¦ ¦Num¦ / ¦ * ¦ - ¦
+-----------------------------------------------------------¦ +---+---+---¦ +---+---+---+---¦
¦ Tab ¦ Q ¦ W ¦ E ¦ R ¦ T ¦ Y ¦ U ¦ I ¦ O ¦ P ¦{ [¦} ]¦ | \ ¦ ¦Del¦End¦PDn¦ ¦ 7 ¦ 8 ¦ 9 ¦ ¦
+-----------------------------------------------------------¦ +-----------+ +---+---+---¦ + ¦
¦ Caps ¦ A ¦ S ¦ D ¦ F ¦ G ¦ H ¦ J ¦ K ¦ L ¦: ;¦" '¦ Enter ¦ ¦ 4 ¦ 5 ¦ 6 ¦ ¦
+-----------------------------------------------------------¦ +---+ +---+---+---+---¦
¦ Shift ¦ Z ¦ X ¦ C ¦ V ¦ B ¦ N ¦ M ¦< ,¦> .¦? /¦ Shift ¦ ¦ ? ¦ ¦ 1 ¦ 2 ¦ 3 ¦ ¦
+--------------------------------------------+--------------¦ +---+---+---+ +-------+---¦ E¦¦
¦ Ctrl¦ Win¦ Alt¦ Space ¦ Alt¦ Win¦Menu¦Ctrl¦ ¦ ? ¦ ? ¦ ? ¦ ¦ 0 ¦ . ¦?-+¦
+-----------------------------------------------------------+ +-----------+ +---------------+
Author: Vo Thanh Hai
*/
typedef long long ll;
using namespace std;

const ll N = 1e5 + 10;
const ll Mod = 123456789;
const ll oo = (ll) 1e18;
const ll LOG = 40;
const ll Base = 29;
const ll NUM = 1e6 + 10;
const double eps = 1e-7;

define db double

define fl float

define i int

define unsigned double

define cin vao

define cout ra

define n "\n"

define ull unsigned long long

define f1 freopen("nguyento.inp","r",stdin);

define f2 freopen("nguyento.out","w",stdout);

define fu(i, a, b) for(int i = a; i <= b; i ++)

define fd(i, a, b) for(int i = a; i >= b; i --)

define sz(s) (ll)s.size()

define mask(s) (1 << (s))

define fs(s) fixed << setprecision(s)

define ALL(s) s.begin(), s.end()

define se second

define fi first

define pll pair<ll, ll>

define plp pair<ll, pll>

define pb push_back

define eb emplace_back

define debug(...) " [" << #VA_ARGS " = " << (VA_ARGS) << "] "

define uni(s) sort(ALL(s)), (s).resize(unique(ALL(s)) - (s).begin())

define lb lower_bound

define ub upper_bound

define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

define Tyo_() signed main()

define tyothankiu return

define tyo2 bool

define tyo3 string

define ins insert

define BIT(x,i) (((1LL<<i)&x)!=0)

define ull unsigned long long

define name "file"

const int mod=int(1e9+7);
int pi[8]={0,0,1,-1,1,1,-1,-1};
int pj[8]={-1,1,0,0,1,-1,1,-1};
template<class A,class B> inline void add(A &a,B b) { a+=b;while (a>=mod) a-=mod;}
template<class A,class B> inline void sub(A &a,B b) { a-=b;while (a>=mod) a-=mod;while (a<0) a+=mod;}
template<class A,class B> bool _max(A &a,B b) {if (a<b) return a=b,1; return 0;} template\<class A,class B> bool _min(A &a,B b) {if (a>b) return a=b,1; return 0;}