cos

void TopSort() {
	int cnt = 0;
    for(グラフ内の各頂点V) 
		if( Indegree[W] == 0)
			Enqueue(V,Q);
	while(!isEmpty(Q)) {
		V = Dequeue(Q);
		出力V,またはVの出力順序を記録,cnt++;
        for(Vの各隣接点W)
        	if(--Indegree[W] == 0)
	            Enqueue(V,Q);
	}
	if(cnt != |V|)
		Error("グラフにサイクルがあります");
}

const int maxn = 1005;
int N,M;//頂点数、辺数（活動数）
int edge[maxn][maxn];
int mint[maxn];//各活動チェックポイントへの最短時間
int In[maxn];//各活動チェックポイントの入次数
void init() {
    memset(edge, -1, sizeof(edge));
    memset(mint, 0, sizeof(mint));
    memset(In, 0, sizeof(In));
}
bool Topsort() {//トポロジカルソート
    queue<int> q;
    for(int i = 0; i < N; ++i) {
        if(In[i] == 0) 
            q.push(i);
    }
    int cnt = 0;
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        cnt++;
        for(int i = 0; i < N; ++i) {
            if(v == i || edge[v][i] == -1) continue;//vを始点とするすべての辺をチェック
            In[i]--;
            //その他の操作
            if(In[i] == 0) q.push(i);
        }
    }
    if(cnt != N) return false;
    else return true;
}

void X_Sort(ElementType A[], int N);

void Bubble_Sort(ll a[], int N) {
    for(int P = N-1; P >= 0; P--) {
        bool flag = false;
        //一回のバブルソート 上から下に比較し、上が下より大きければ交換
        for(int i = 0; i < P; ++i) {    
            if(a[i] > a[i+1]) {
                swap(a[i], a[i+1]);
                flag = true;
            }
        }
        if(!flag) break; //一回の処理で既に整列されている場合、交換は発生しない
    }
}

void Insertion_Sort(ll a[], int N) {
    for(int P = 1; P < N; P++) {
        ll t = a[P];//次のカードを引く
        int i;
        for(i = P; i > 0 && a[i-1] > t; --i) 
            a[i] = a[i-1];  //空き位置を移動 その前の要素が現在の要素より小さくなるまで
        a[i] = t;   //新しいカードを配置
    }
}

void Shell_Sort(ll a[], int N) {
    for(int D = N/2; D > 0; D /= 2) { //シェル増分列
        for(int P = D; P < N; ++P) { //挿入ソート
            ll t = a[P];
            int i;
            for(i = P; i >= D && a[i-D] > t; i -= D) 
                a[i] = a[i-D];
            a[i] = t;
        }
    }
}

void Selection_Sort(ll a[], int N) {
    for(int i = 0; i < N; ++i) {
        int mini = 0;
        ll ans = inf;
        //iの後ろで最小の要素を探し、その位置をminiに代入
        for(int j = i; j <= N-1; ++j) {
            if(a[j] < ans) {
                ans = a[j];
                mini = j;
            }
        }
        //未ソート部分の最小要素をソート済み部分の最後の位置に移動
        swap(a[i], a[mini]);
    }
}

void swap(ll& x, ll& y) {
    ll t = x;
    x = y;
    y = t;
}
void PercDown(ll a[], int N, int rt) {
    //N個の要素の配列において、a[now]を根とする部分ヒープを最大ヒープに調整
    int father, son;
    ll tmp = a[rt];
    for(father = rt; (father*2+1) < N; father = son) {
        son = father * 2 + 1;//左の子
        if(son != N-1 && a[son] < a[son+1]) //右の子が存在し、左の子より大きい
            son++;
        if(tmp >= a[son]) break;//配置すべき場所を見つける
        else a[father] = a[son];//下にフィルタリング
    }
    a[father] = tmp;
}
inline void BuildHeap(ll a[], int N) {
    for(int i = N/2-1; i >= 0; --i) {
        PercDown(a, N, i);
    }
}
void Heap_Sort(ll a[], int N) {
    BuildHeap(a, N);
    for(int i = N-1; i > 0; --i) {
        swap(a[0], a[i]);//最大ヒープの頂点a[0]とa[i]を交換
        PercDown(a, i, 0);//削除後に調整
    }
}

void Merge(ll a[], int s, int m, int e, ll tmp[]) {
    //配列aの局所a[s,m]とa[m+1,e]をtmp配列にマージし、tmpをソートされた状態に保ちます。
    //その後、再びa[s,m]にコピーします。時間計算量O(e-m+1)、すなわちO(n)です。
    int pb = s;//pbはtmp配列のインデックス
    int p1 = s, p2 = m+1;//p1は前半、p2は後半を指します
    while (p1 <= m && p2 <= e) {
        if (a[p1] < a[p2])
            tmp[pb++] = a[p1++];
        else 
            tmp[pb++] = a[p2++];
    }
    while(p1 <= m) 
        tmp[pb++] = a[p1++];
    while(p2 <= e) 
        tmp[pb++] = a[p2++];
    for (int i = 0; i < e-s+1; ++i)
        a[s+i] = tmp[i];
}
void MergeSort(ll a[], int s, int e, ll tmp[]) {
    if (s < e) {//s>=eの場合は何もしません
        int m = s + (e-s)/2;
        MergeSort(a, s, m, tmp);//前半をソート
        MergeSort(a, m+1, e, tmp);//後半をソート
        Merge(a, s, m, e, tmp);//マージ aのsからmとm+1からeの2つの配列をソートされた状態でマージ
    }
}

void QuickSort(ll a[], int s, int e){//a[s,e]をクイックソート
    if (s >= e)
        return;
    int k = a[s];
    int i = s,j = e;
    while (i != j) {
        while (j > i && a[j] >= k)  --j;
        swap(a[i],a[j]);
        while (i < j && a[i] <= k)  ++i;
        swap(a[i],a[j]);
    }//処理が終わった後a[i] = k;
    QuickSort(a, s, i-1);//左側の部分をクイックソート
    QuickSort(a, i+1, e);//右側の部分をクイックソート
}

ll getMax(ll a[], int n) {//n個の要素のa配列から最大数を見つける
    int maxx = a[0];
    for(int i = 1; i < n; ++i) {
        if(a[i] > maxx) maxx = a[i];
    }
    return maxx;
}
void radixsort(ll a[], int n, int exp) { //n個の要素の配列aを「ある位数」に従ってソート（バケットソート）、基数は10
    ll tmp[maxn];
    ll T[20] = {0}; //負数のある10進数 二十個のバケット
    for(int i = 0; i < n; ++i) //Tにそのバケットにいくつの数があるかを格納
        T[(a[i]/exp)%10 + 10]++;
    for(int i = 1; i < 20; ++i) //Tの値をtmp内の位置にする
        T[i] += T[i-1];
    for(int i = n - 1; i >= 0; --i) {
        int now = T[(a[i]/exp)%10 + 10];//現在の数が配置されるべき位置
        tmp[now-1] = a[i];
        T[(a[i]/exp)%10 + 10]--;
    }
    for(int i = 0; i < n; ++i)
        a[i] = tmp[i]; //ソートされたtmpをaに代入
}
void Radix_Sort(ll a[], int n) {
    ll maxnum = getMax(a, n);
    for(int exp = 1; maxnum/exp > 0; exp *= 10) 
        radixsort(a, n, exp);
}