#define INF 0x3f3f3f
const int MAXN = 1000;
/**
 * 欧拉函数
 * @param n 一个整数
 * @return 质因数个数
 */
int eular(int n) {
    int r = 1;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i ==0) {
            n /= i;
            r *= i - 1;
            while (n % i == 0) {
                n /= i;
                r *= i;
            }
        }
    }
    if (n > 1) r *= n - 1;
    return  r;
}
/**
 * 约瑟夫问题
 * @param n 总人数
 * @param m 出队报数
 */
void joseph(int n, int m) {
    list<int> l;
    for (int i = 1; i <= n; ++i) {
        l.push_back(i);
    }
    auto it = l.begin();
    while (l.size() > 1) {
        for (int j = 1; j < m; ++j) {
            ++it;
            if (it == l.end()) it = l.begin();
        }
    it = l.erase(it);
    if (it == l.end()) it = l.begin();
    }
    cout << *it << endl;
}
/**
 * 波兰表达式
 * @return 表达式结果
 */
double poland() {
    string s;
    cin >> s;
    switch (s[0]) {
        case '+': return poland() + poland();
        case '-': return poland() - poland();
        case '*': return poland() * poland();
        case '/': return poland() / poland();
        default: return stod(s);
    }
}

int cnt = 0;
/**
 * 汉诺塔算法
 * @param n 编号
 * @param x x柱
 * @param y y柱
 * @param z z柱
 */
void hanoi(int n, char x, char y, char z) {
    if (n == 1) {
        printf("%d %d %c=>%c\n", cnt++, n, x, z);
    }
    else {
        hanoi(n - 1, x, z, y);
        printf("%d %d %c=>%c\n", cnt++, n, x, z);
        hanoi(n - 1, y, x, z);
    }
}
struct Edge {
    int from, to, cost;
    Edge(int u, int v, int w) : from(u), to(v), cost(w) {}
    bool operator< (const Edge& x) const {
        return cost < x.cost;
    }
};
struct HeapNode {
    int d, u; // d表示点u到MST的距离
    bool operator< (const HeapNode& rhs) const {
        return d > rhs.d;
    }
    HeapNode(int d, int u) : d(d), u(u) {}
};
vector<Edge> edges; // edges存所有边
vector<int> G[MAXN]; // G[i]是顶点i发出的所有边
/**
 * for (int i = 0; i < E; ++i) { // E是边数
 *  int u, v, cost;
 *  cin >> u >> v >> cost;  // 输入边的起点、终点和权值
 *  G[u].push_back(i);  // 存储边的索引
 *  edges.push_back(Edge(u, v, cost));
 *  G[v].push_back(i);  // 存储边的索引
 *  edges.push_back(Edge(v, u, cost));
 * }
 */
bool done[MAXN]; // i是否已经加入了T
int d[MAXN]; // 每个点到T的最小距离
/**
 * Prim算法
 * @param V 顶点数
 * @return 最小生成树长度
 */
int Prim(int V) {
   priority_queue<HeapNode> Q;
   int ans = 0;
   for (int i = 0; i < V; ++i) {
       d[i] = INF;
   }
   d[0] = 0;
   memset(done, 0, sizeof(done));
   Q.emplace(0, 0);
   while (!Q.empty()) {
       HeapNode x = Q.top();
       Q.pop();
       int u = x.u;
       if (done[u]) continue;
       ans += x.d;
       done[u] = true;
       for (int i : G[u]) {
           Edge& e = edges[i];
           if (d[e.to] > e.cost) {
               d[e.to] = e.cost;
               Q.emplace(d[e.to], e.to);
           }
       }
   }
    return ans;
}
/**
 * 并查集
 */
class UnionFind{
private:
    vector<int> par; // 存储父节点
public:
    UnionFind(int V) {
        for (int i = 0; i < V; ++i) {
            par.emplace_back(i);
        }
    }
    /**
     * 查找根节点
     * @param x 待查节点
     * @return 根节点
     */
    int find(int x) {
        if (par[x] == x) return x;
        else return par[x] = find(par[x]);
    }
    /**
     * 合并
     * @param x
     * @param y
     */
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            par[x] = y;
        }
    }
    /**
     * 判断是否连通
     * @param x
     * @param y
     * @return 是否连通
     */
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};
/**
 * Kruskal算法
 * @param V 顶点数
 * @return 最小生成树长度
 */
int Kruskal(int V) {
    sort(edges.begin(), edges.end());
    UnionFind UF = UnionFind(V);
    int ans = 0;
    for (Edge e : edges) {
        if (!UF.same(e.from, e.to)) {
            UF.unite(e.from, e.to);
            ans += e.cost;
        }
    }
    return ans;
}
int path[MAXN]; // 记录到顶点i的是哪条边
/**
 * Dijkstra算法 计算所有顶点到顶点s的最短路径
 * @param s 顶点s
 * @param V 顶点数
 */
void Dijkstra(int s, int V) {
    priority_queue<HeapNode> Q;
    for (int i = 0; i < V; ++i) d[i] = INF;
    d[s] = 0;
    memset(done, 0 ,sizeof(done));
    Q.emplace(0, s);
    while (!Q.empty()) {
        HeapNode x = Q.top();
        Q.pop();
        int u = x.u;
        if (done[u]) continue;
        done[u] = true;
        for (int i : G[u]) {
            Edge& e = edges[i];
            if (d[e.to] > d[u] + e.cost) {
                d[e.to] = d[u] + e.cost;
                path[e.to] = i;
                Q.emplace(d[e.to], e.to);
            }
        }
    }
}
int dis[MAXN][MAXN]; // 距离矩阵
int p[MAXN][MAXN]; // 路径数组
/**
 * FloydWarshall算法 计算全源最短路径
 * @param V 顶点数
 */
void FloydWarshall(int V) {
    // 初始化距离数组
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (i == j) dis[i][j] = 0;
            else dis[i][j] = INF;
            p[i][j] = -1;
        }
    }
    // 更新距离矩阵
    for (Edge e : edges) {
        if (dis[e.from][e.to] > e.cost) {
            dis[e.from][e.to] = e.cost;
            p[e.from][e.to] = e.from;
        }
    }
    // 计算最短路径
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dis[i][k] != INF && dis[k][j] != INF && dis[i][j] > dis[i][k] + dis[k][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    p[i][j] = p[k][j];
                }
            }
        }
    }
}

/**
 * 拓扑排序
 * @param V
 * @return 拓扑序列
 */
vector<int> TopologicalSort(int V) {
    int inDegree[MAXN];
    vector<int> result;
    queue<int> Q;
    for (Edge e : edges) {
        inDegree[e.to]++;
    }
    for (int i = 0; i < V; ++i) {
        if (inDegree[i] == 0) Q.emplace(i);
    }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        result.emplace_back(u);
        for (int i : G[u]) {
            Edge& e = edges[i];
            int v = e.to;
            if (--inDegree[v] == 0) {
                Q.emplace(v);
            }
        }
    }
}
/**
 * 小根堆
 */
class MinHeap {
private:
    vector<int> a;
public:
    /**
     * 调整堆
     * @param i 传入节点下标
     */
    void adjustHeap(int i) {
        int n = a.size();
        int lChild = i * 2 + 1;
        int rChild = i * 2 + 2;
        int minI = i;
        if (lChild < n && a[lChild] < a[minI]) {
            minI = lChild;
        }
        if (rChild < n && a[rChild] < a[minI]) {
            minI = rChild;
        }
        if (minI != i) {
            swap(a[minI], a[i]);
            adjustHeap(minI);
        }
    }
    /**
     * 构造函数
     * @param b 原始数组
     */
    MinHeap(const vector<int>& b) {
        a = b;
        int n = b.size();
        for (int i = n / 2 - 1; i >= 0; --i) {
            adjustHeap(i);
        }
    }
};