import java.util.Scanner;

public class Main {
    public static void debug(Object ... objs){
        System.out.println(Arrays.toString(objs));
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // input here
        sc.close();
    }
}

public static class Scanner implements AutoCloseable {
    private BufferedReader br;
    private StringTokenizer tok;

    public Scanner(InputStream is) {
        br = new BufferedReader(new InputStreamReader(is));
    }

    private void getLine() {
        try {
            while (!hasNext()) {tok = new StringTokenizer(br.readLine());}
        } catch(IOException e){ /* ignore */ }
    }

    private boolean hasNext() {
        return tok != null && tok.hasMoreTokens();
    }

    public String next() {
        getLine(); return tok.nextToken();
    }

    public int nextInt(){
        return Integer.parseInt(next());
    }
    // 他のnextXXXもXXX.parseXXX()メソッドを使って作れるので省略

    public void close() {
        try{ br.close(); } catch (IOException e){ /*ignore*/ }
    }
}

public static final int INF = Integer.MAX_VALUE / 2 - 1;

public static final long INF = Long.MAX_VALUE / 2 - 1;

public static final double EPS = 1e-9;

public static <T> void swap(T[] array, int fst, int snd){
    T tmp = array[fst];
    array[fst] = array[snd];
    array[snd] = tmp;
}

public static <T> void reverse(T[] array, int begin, int end){ // [begin, end)
    for(int i = begin, j = end - 1; i < j; i++, j--) { swap(array, i, j); }
}

public static <T extends Comparable<? super T>> int upper_bound(T[] array, T key){
    int lower = -1, upper = array.length;
    // keep array[lower] <= key && key < array[upper]
    while(upper - lower > 1){
        final int mid = (lower + upper) / 2;
        final int comp = array[mid].compareTo(key);

        if(comp <= 0){ lower = mid; }
        else if(comp > 0){ upper = mid;}
    }

    return upper;
}

public static <T extends Comparable<? super T>> int lower_bound(T[] array, T key){
    int lower = -1, upper = array.length;
    // keep array[lower] < key && key <= array[upper]
    while(upper - lower > 1){
        final int mid = (lower + upper) / 2;
        final int comp = array[mid].compareTo(key);

        if(comp < 0){ lower = mid; }
        else if(comp >= 0){ upper = mid;}
    }

    return upper;
}

public static class UnionFind{
    int[] par; //
    
    public UnionFind(int n){
        par = new int[n];
        for(int i = 0; i < n; i++){ par[i] = -1; }
    }
    
    public int find(int x){
        if(par[x] < 0){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    }
    
    public boolean union(int x, int y){
        x = find(x);
        y = find(y);
        
        if(x != y){
            if(par[y] < par[x]) {  // 多い方が根になるようにスワップする.
                int tmp = x; x = y; y = tmp;
            }
            par[x] += par[y];
            par[y] = x;
            return true;
        }else{
            return false;
        }
    }
    
    public boolean same(int x, int y){
        return find(x) == find(y);
    }
    
    public int size(int x){
        return -par[find(x)];
    }
}

public static class WeightedUnionFind{
    int[] par; // 親の番号
    int[] ws;  // 親との重みの差
    
    public WeightedUnionFind(int n){
        par = new int[n];
        ws  = new int[n];
        for(int i = 0; i < n; i++){ par[i] = -1; }
    }
    
    public int find(int x){
        if(par[x] < 0){
            return x;
        }else{
            final int parent = find(par[x]);
            ws[x] += ws[par[x]];
            return par[x] = parent;
        }
    }
    
    public int weight(int x){
        find(x); 
        return ws[x];
    }
    
    public boolean union(int x, int y, int w){ // x <-(w)- y (x + w = y)
        w += weight(x); 
        w -= weight(y);
        x = find(x); y = find(y);
        
        if(x != y){
            if(par[y] < par[x]) {  // 多い方が根になるようにスワップする.
                int tmp = x; x = y; y = tmp; w = -w;
            }
            par[x] += par[y]; par[y] = x;
            ws[y] = w;
            return true;
        }else{
            return false;
        }
    }
    
    public boolean same(int x, int y){
        return find(x) == find(y);
    }
    
    public Integer diff(int x, int y){ // x - y を求める. 比較不能ならnull.
        if(!same(x, y)){ return null; }
        return this.weight(x) - this.weight(y);
    }
    // size()はUnionFindと同じなので省略.
}

public static class SegTree{
    int n;
    long[] dat;

    public SegTree(int n_) {
        int n = 1;
        while(n < n_){
            n *= 2;
        }

        this.n = n;
        dat = new long[this.n * 2 - 1];
        for(int i = 0; i < this.n * 2 - 1 ; i++){
            dat[i] = 0;
        }
    }

    public long calc(long fst, long snd){ return fst + snd; }

    public void update(int k, long a){
        k += n - 1;
        dat[k] = a;

        while(k > 0){
            k = (k - 1) / 2;
            dat[k] = calc(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }

    public long query(int a, int b, int k, int l, int r){
        if(r <= a || b <= l){
            return 0;
        }else if(a <= l && r <= b){
            return dat[k];
        }else {
            return calc(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2 , (l + r) / 2, r));
        }
    }

    public long query(int a, int b){
        return query(a, b, 0, 0, n);
    }
}

public static class BIT {
    int[] dat;
    
    public BIT(int n){
        dat = new int[n + 1];
    }
    
    public void add(int k, int a){ // k : 0-indexed
        for(int i = k + 1; i < dat.length; i += i & -i){
            dat[i] += a;    
        }
    }
    
    public int sum(int s, int t){ // [s, t)
        if(s > 0) return sum(0, t) - sum(0, s);
        
        int ret = 0;
        for(int i = t; i > 0; i -= i & -i) {
            ret += dat[i];
        }
        return ret;
    }
}

public static class SegTree {
    private static final long DEFAULT = 0; // 単位元

    private long lower, upper; // [lower, upper)
    private SegTree left, right;
    private long value = DEFAULT; // 初期値は単位元

    public SegTree(final long n){ this(0, Long.highestOneBit(n) << 1l); }

    private SegTree(long lower, long upper){ this(lower, upper, DEFAULT); }
    private SegTree(final long lower, final long upper, final long value){
        this.lower = lower; this.upper = upper; this.value = value;
    }

    private static long get(SegTree s){return s==null ? DEFAULT : s.value;}

    public SegTree update(final long index, final long value){
        if(this.lower == index && this.upper == index + 1){
            return new SegTree(index, index + 1, value);
        }else{// split to [lower, middle) and [middle, upper)
            final long middle = (this.lower + this.upper) / 2;
            final SegTree ret = new SegTree(this.lower, this.upper);

            if(index < middle){ //update in [lower, middle)
                ret.left = this.left != null ? this.left
                        : new SegTree(this.lower, middle);
                ret.left = ret.left.update(index, value);
                ret.right = right;
            }else{ //update in [middle, upper)
                ret.left = this.left;
                ret.right = this.right != null ? this.right
                        : new SegTree(middle, this.upper);
                ret.right = ret.right.update(index, value);
            }
            ret.value = get(ret.left) + get(ret.right);

            return ret;
        }
    }

    public long query(long lower, long upper){
        if(this.upper <= lower || upper <= this.lower){
            return DEFAULT;
        }else if(lower <= this.lower && this.upper <= upper){
            return this.value;
        }
        final long middle = (this.lower + this.upper) / 2;
        return (left == null ? DEFAULT : left.query(lower, middle))
            + (right == null ? DEFAULT : right.query(middle, upper));
    }
}

public static class LazyAddSumSegmentTree{
    int n;
    long[] dat, lazy;

    public LazyAddSumSegmentTree(int n_) {
        int n = 1;
        while(n < n_){ n *= 2;} this.n = n;
        dat = new long[this.n * 2 - 1];
        lazy = new long[this.n * 2 - 1];
    }

    private void evaluate_lazy(int k, int l, int r){
        dat[k] += lazy[k] * (r - l);
        if(k < n - 1){
            lazy[2 * k + 1] += lazy[k]; lazy[2 * k + 2] += lazy[k];
        }
        lazy[k] = 0;
    }

    public void update_node(int k){ dat[k] = dat[2*k+1] + dat[2*k+2]; }

    public void add(long v, int a, int b){ add(v, a, b, 0, 0, this.n); }
    public void add(long v, int a, int b, int k, int l, int r){
        evaluate_lazy(k, l, r);

        if(r <= a || b <= l){ return;
        }else if(a <= l && r <= b){
            lazy[k] += v; evaluate_lazy(k, l, r);
        }else {
            add(v, a, b, k * 2 + 1, l , (l + r) / 2);
            add(v, a, b, k * 2 + 2, (l + r) / 2, r);
            update_node(k);
        }
    }

    public long sum(int a, int b){ return sum(a, b, 0, 0, this.n); }
    public long sum(int a, int b, int k, int l, int r){
        evaluate_lazy(k, l, r);

        if(r <= a || b <= l){ return 0;
        }else if(a <= l && r <= b){ return dat[k];
        }else {
            long v1 = sum(a, b, k * 2 + 1, l , (l + r) / 2);
            long v2 = sum(a, b, k * 2 + 2, (l + r) / 2, r);
            update_node(k); return v1 + v2;
        }
    }
}

public static class LazySetSumSegmentTree {
    int n;
    long[] dat, lazy;
    boolean[] push;

    public LazySetSumSegmentTree(int n_) {
        int n = 1;
        while(n < n_){ n *= 2;} this.n = n;
        dat = new long[this.n * 2 - 1];
        lazy = new long[this.n * 2 - 1];
        push = new boolean[this.n * 2 - 1];
    }

    private void evaluate_lazy(int k, int l, int r){
        if(!push[k]){ return; }
        dat[k] = lazy[k] * (r - l);
        if(k < n - 1){
            lazy[k * 2 + 1] = lazy[k * 2 + 2] = lazy[k];
            push[k * 2 + 1] = push[k * 2 + 2] = true;
        }
        lazy[k] = 0; push[k] = false;
    }

    private void update_node(int k){ dat[k] = dat[k*2+1] + dat[k*2+2]; }

    public void set(long v, int a, int b){ set(v, a, b, 0, 0, this.n); }
    public void set(long v, int a, int b, int k, int l, int r){
        evaluate_lazy(k, l, r);
        if(r <= a || b <= l){ return;
        }else if(a <= l && r <= b){
            lazy[k] = v; push[k] = true;
            evaluate_lazy(k, l, r);
        }else{
            set(v, a, b, k * 2 + 1, l, (l + r) / 2);
            set(v, a, b, k * 2 + 2, (l + r) / 2, r);
            update_node(k);
        }
    }
    
    public long sum(int a, int b){ return sum(a, b, 0, 0, this.n); }
    public long sum(int a, int b, int k, int l, int r){
        evaluate_lazy(k, l, r);
        if(r <= a || b <= l){ return 0;
        }else if(a <= l && r <= b){ return dat[k];
        }else{
            final long v1 = sum(a, b, k * 2 + 1, l, (l + r) / 2);
            final long v2 = sum(a, b, k * 2 + 2, (l + r) / 2, r);
            update_node(k); return v1 + v2;
        }
    }
}

// 初期値は [0,n) = 0, 範囲minが手抜きなので,番兵(INF)が必要.
public static class RMQ {
    private static final long INF = Long.MAX_VALUE / 2 - 1;
    private static final long DEFAULT = 0; // 単位元

    int n; long[] min, add; // add[k]...範囲に足した値. min[k]...その時点での最小値

    public RMQ(int n_) {
        int n = 1;
        while(n < n_){ n *= 2;} this.n = n;
        min = new long[this.n * 2 - 1]; add = new long[this.n * 2 - 1];
        for(int i = 0; i < this.n * 2 - 1 ; i++){
            min[i] = DEFAULT; add[i] = DEFAULT;
        }
    }

    // [a, b) に v を足す
    public void add(long v, int a, int b){ add(v, a, b, 0, 0, this.n); }
    private void add(long v, int a, int b, int k, int l, int r){
        if(r <= a || b <= l){ return; } // 完全に範囲外
        if(a <= l && r <= b) { // 完全に範囲内
            add[k] += v;
        }else{ //範囲外を含む -> 二分割して再帰
            add(v, a, b, k * 2 + 1, l, (l + r) / 2);
            add(v, a, b, k * 2 + 2, (l + r) / 2, r);
        }
        min[k] = (k >= (n - 1) ? DEFAULT : Math.min(min[k * 2 + 1], min[k * 2 + 2])) + add[k];
    }

    // [a, b) の範囲での最小値を求める
    public long min(long a, long b){ return min(a, b, 0, 0, this.n); }
    private long min(long a, long b, int k, int l, int r){
        if(r <= a || b <= l){ return INF; } // 簡単のため適当に大きい値を返す.
        if(a <= l && r <= b){ return min[k]; } //

        final long left_min  = min(a, b, k * 2 + 1, l, (l + r) / 2);
        final long right_min = min(a, b, k * 2 + 2, (l + r) / 2, r);
        return Math.min(left_min, right_min) + add[k]; //
    }

    // [index] での値を求める
    public long value(int index){
        int k = index + this.n - 1;
        long value = add[k];
        while(k > 0){ k = (k - 1) / 2; value += add[k]; }
        return value;
    }
}

// JOI界隈で人気な, ちょっと特殊なRMQ(Range Maximum Query).
// 根は全体の最大値, 子ノードのうちどちらかは 0, もう一方は 0 以下を満たす.
public static class StarrySkyTree {
    private static final long M_INF = Long.MIN_VALUE / 2 + 1;
    private static final long DEFAULT = 0; // 単位元

    int n; long[] add; //addは上記の制約を満たす.

    public StarrySkyTree(int n_) {
        int n = 1;
        while(n < n_){ n *= 2;} this.n = n;
        add = new long[this.n * 2 - 1];
        for(int i = 0; i < this.n * 2 - 1 ; i++){ add[i] = DEFAULT; }
    }

    // [a, b) に v を足す
    public void add(long v, int a, int b){ add(v, a, b, 0, 0, this.n); }
    private void add(long v, int a, int b, int k, int l, int r){
        if(k == 0){ add[k] += v; } // 全体に加算しておく.
        if(a <= l && r <= b) { return; } // 完全に範囲内
        if(r <= a || b <= l) { add[k] -= v; return; } // 完全に範囲外
        // 範囲外を含む -> 二分割して再帰
        add(v, a, b, k * 2 + 1, l, (l + r) / 2);
        add(v, a, b, k * 2 + 2, (l + r) / 2, r);
        // どちらかが 0 になるように, 子供の最大値を子供から引いて親に足す.
        final long child_max = Math.max(add[k * 2 + 1], add[k * 2 + 2]);
        add[k * 2 + 1] -= child_max; add[k * 2 + 2] -= child_max;
        add[k] += child_max;
    }

    // [a, b) の範囲での最大値を求める
    public long max(long a, long b){ return max(a, b, 0, 0, this.n); }
    private long max(long a, long b, int k, int l, int r){
        if(r <= a || b <= l){ return M_INF; } // 簡単のため適当に小さい値を返す.
        if(a <= l && r <= b){ return add[k]; } // 子孫のaddは 0 を選べる.

        final long left_max  = max(a, b, k * 2 + 1, l, (l + r) / 2);
        final long right_max = max(a, b, k * 2 + 2, (l + r) / 2, r);
        return Math.max(left_max, right_max) + add[k]; //
    }

    // [index] での値を求める
    public long value(int index){
        int k = index + this.n - 1;
        long value = add[k];
        while(k > 0){ k = (k - 1) / 2; value += add[k]; }
        return value;
    }
}

public static class RMQ {
    long[][] sparse_table; // queryを O(1)にするなら, k をメモ化する事.

    public RMQ(long[] array){ // O(n log n)
        final int depth = Integer.numberOfTrailingZeros(Integer.highestOneBit(array.length));
        sparse_table = new long[depth + 1][]; sparse_table[0] = new long[array.length];
        System.arraycopy(array, 0, sparse_table[0], 0, array.length);

        for(int k = 1; k < sparse_table.length; k++){
            sparse_table[k] = new long[array.length - (1 << k) + 1];
            for(int i = 0; i + (1 << k) <= array.length; i++) { // [i, i + (1 << k))
                // [i, i + (1 << k) -> [i, i + (1 << k) / 2), [i + (1 << k) / 2, i << (k - 1))
                sparse_table[k][i] =
                        Math.min(sparse_table[k-1][i], sparse_table[k-1][i + (1 << (k - 1))]);
            }
        }
    }

    public void update(int index, long v){ // index: 0-index
        //update O(n log n) で効率が悪い. SegTreeでどうぞ.
        sparse_table[0][index] = v;
        for(int k = 1; k < sparse_table.length; k++){
            final int begin = Math.max(0, index - (1 << k) + 1);
            final int end = Math.min(sparse_table[k].length, index + (1 << k));
            // 最大で index + [-(1 << k) + 1, (1 << k)) の範囲を更新する必要がある
            for(int i = begin; i < end; i++){
                sparse_table[k][i] =
                        Math.min(sparse_table[k - 1][i], sparse_table[k-1][i + (1 << (k - 1))]);
            }
        }
    }

    public long query(int l, int r){ // [l, r) O(log log n)
        final int k = Integer.numberOfTrailingZeros(Integer.highestOneBit(r - l));
        // k -> 区間をオーバーしない最大の2の冪乗
        // left -> [i, i + (1 << k)), right -> [r - (1 << k)] (開区間なので±0)
        return Math.min(sparse_table[k][l], sparse_table[k][r - (1 << k)]);
    }
}

// SegmentTree(っぽい) 構造で範囲内のn番目の最小値を求める.
public static class RMNthQ {
    int n, depth;
    long[][] segs;

    public RMNthQ(int n_) {
        this.n = n_;
        this.depth = Integer.numberOfTrailingZeros(Integer.highestOneBit(n_)) + 2;
        segs = new long[depth][n_];
    }

    private void merge(int d, int begin, int middle, int end){
        for(int d_pos = begin, s1_pos = begin, s2_pos = middle; d_pos < end; d_pos++){
            if(s1_pos >= middle){ segs[d][d_pos] = segs[d + 1][s2_pos++]; }
            else if(s2_pos >= end) { segs[d][d_pos] = segs[d + 1][s1_pos++]; }
            else if(segs[d + 1][s1_pos] <= segs[d + 1][s2_pos]) {
                segs[d][d_pos] = segs[d + 1][s1_pos++];
            }else{
                segs[d][d_pos] = segs[d + 1][s2_pos++];
            }
        }
    }

    public void init(long[] array){ // O( n log n)
        System.arraycopy(array, 0, segs[depth - 1], 0, n);
        for(int d = depth - 2, size = 2; d >= 0; d--, size *= 2){
            for(int begin = 0; begin < this.n; begin += size){
                final int middle = begin + size / 2;
                final int end = Math.min(begin + size, this.n);

                this.merge(d, begin, middle, end);
            }
        }
    }

    public void update(int k, long a){ // 多分 O(n)
        segs[depth - 1][k] = a;
        for(int d = depth - 2, size = 2; d >= 0; d--, size *= 2){
            final int begin = (k / size) * size, middle = begin + size / 2;
            final int end  = Math.min(begin + size, this.n);

            this.merge(d, begin, middle, end);
        }
    }

    private static int upper_bound(long[] array, long key, int begin, int end){
        int lower = begin - 1, upper = end;
        while(upper - lower > 1){
            final int mid = (lower + upper) / 2;

            if(array[mid] <= key){ lower = mid; } else { upper = mid;}
        }
        return upper;
    }

    public int query(int a, int b, long v, int d, int l, int r){ // O(log^2 n)
        if(r <= a || b <= l){
            return 0;
        }else if(a <= l && r <= b){
            return (upper_bound(segs[d], v, l, r) - l);
        }else {
            final int size = 1 << (depth - d - 1);
            return query(a, b, v, d + 1, l, l + size / 2)
                    + query(a, b, v, d + 1, l + size / 2, Math.min(l + size, n));
        }
    }

    public long query(int a, int b, int nth){ // O(log^3 n)
        int lower_index = -1, upper_index = this.n; //(l, u]
        while(upper_index > lower_index + 1) {
            final int middle_index = (lower_index + upper_index) / 2;
            final int ret = query(a, b, segs[0][middle_index], 0, 0, this.n);
            if (ret < nth) { lower_index = middle_index; }
            else { upper_index = middle_index; }
        }
        return segs[0][upper_index];
    }
}

// SegmentTree(っぽい) 構造で範囲内のn番目の最小値を求める.
public static class RMNthQ {
    int n, depth;
    long[][] segs;

    public RMNthQ(int n_) {
        this.n = n_;
        this.depth = Integer.numberOfTrailingZeros(Integer.highestOneBit(n_)) + 2;
        segs = new long[depth][n_];
    }

    private void merge(int d, int begin, int middle, int end){
        for(int d_pos = begin, s1_pos = begin, s2_pos = middle; d_pos < end; d_pos++){
            if(s1_pos >= middle){ segs[d][d_pos] = segs[d + 1][s2_pos++]; }
            else if(s2_pos >= end) { segs[d][d_pos] = segs[d + 1][s1_pos++]; }
            else if(segs[d + 1][s1_pos] <= segs[d + 1][s2_pos]) {
                segs[d][d_pos] = segs[d + 1][s1_pos++];
            }else{
                segs[d][d_pos] = segs[d + 1][s2_pos++];
            }
        }
    }

    public void init(long[] array){ // O( n log n)
        System.arraycopy(array, 0, segs[depth - 1], 0, n);
        for(int d = depth - 2, size = 2; d >= 0; d--, size *= 2){
            for(int begin = 0; begin < this.n; begin += size){
                final int middle = begin + size / 2;
                final int end = Math.min(begin + size, this.n);

                this.merge(d, begin, middle, end);
            }
        }
    }

    public void update(int k, long a){ // 多分 O(n)
        segs[depth - 1][k] = a;
        for(int d = depth - 2, size = 2; d >= 0; d--, size *= 2){
            final int begin = (k / size) * size, middle = begin + size / 2;
            final int end  = Math.min(begin + size, this.n);

            this.merge(d, begin, middle, end);
        }
    }

    private static int upper_bound(long[] array, long key, int begin, int end){
        int lower = begin - 1, upper = end;
        while(upper - lower > 1){
            final int mid = (lower + upper) / 2;

            if(array[mid] <= key){ lower = mid; } else { upper = mid;}
        }
        return upper;
    }

    public int query(int a, int b, long v, int d, int l, int r){ // O(log^2 n)
        if(r <= a || b <= l){
            return 0;
        }else if(a <= l && r <= b){
            return (upper_bound(segs[d], v, l, r) - l);
        }else {
            final int size = 1 << (depth - d - 1);
            return query(a, b, v, d + 1, l, l + size / 2)
                    + query(a, b, v, d + 1, l + size / 2, Math.min(l + size, n));
        }
    }

    public long query(int a, int b, int nth){ // O(log^3 n)
        int lower_index = -1, upper_index = this.n; //(l, u]
        while(upper_index > lower_index + 1) {
            final int middle_index = (lower_index + upper_index) / 2;
            final int ret = query(a, b, segs[0][middle_index], 0, 0, this.n);
            if (ret < nth) { lower_index = middle_index; }
            else { upper_index = middle_index; }
        }
        return segs[0][upper_index];
    }
}

// INF という値は適当に大きい値を突っ込んでおく.
// 二つ足しても平気な Long.MAX_VALUE / 2 - 1 を良く使う.
public static long[][] init_adj(final int n){
    long[][] ret = new long[n][n];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            ret[i][j] = i == j ? 0 : INF;
        }
    }
    return ret;
}

public static ArrayList<Map<Integer, Long>> init_adj(final int n){
    ArrayList<Map<Integer, Long>> ret = new ArrayList<Map<Integer, Long>>();
    for(int i = 0; i < n; i++){
        ret.add(new LinkedHashMap<Integer, Long>());
    }
    return ret;
}

public static final int unvisited = 0, visiting = 1, visited = 2;

public static boolean dfs(int node, boolean[][] adj, int[] state){
    state[node] = visiting;

    for(int i = 0; i < adj.length; i++){
        if(!adj[node][i]){ continue; }
        else if(state[i] == unvisited){
            if(!dfs(i, adj, state)){ //
                state[node] = visited; return false;
            }
        }else if(state[i] == visiting){ //cycle!
            return false;
        }
    }

    state[node] = visited;
    return true;
}

public static boolean find_cycle(boolean[][] adj){
    int[] state = new int[adj.length];
    for(int i = 0; i < adj.length; i++){
        state[i] = unvisited;
    }
    for(int i = 0; i < adj.length; i++){
        if(state[i] == unvisited){
            if(!dfs(i, adj, state)){
                return false;
            }
        }
    }
    return true;
}

public static final int unvisited = 0, visiting = 1, visited = 2;

public static boolean dfs(int node, boolean[][] adj, int[] state, LinkedList<Integer> list){
    state[node] = visiting;

    for(int i = 0; i < adj.length; i++){
        if(!adj[node][i]){ continue; }
        else if(state[i] == unvisited){
            if(!dfs(i, adj, state, list)){ //
                state[node] = visited; return false;
            }
        }else if(state[i] == visiting){ //cycle!
            return false;
        }
    }

    state[node] = visited;
    list.addFirst(node);
    return true;
}

public static boolean topological_sort(boolean[][] adj, LinkedList<Integer> list){
    int[] state = new int[adj.length];
    for(int i = 0; i < adj.length; i++){
        state[i] = unvisited;
    }
    for(int i = 0; i < adj.length; i++){
        if(state[i] == unvisited){
            if(!dfs(i, adj, state, list)){
                return false;
            }
        }
    }
    return true;
}

// next[i][j] := i -> j へ行く際に, 次に通過する点
// for(int cur = start; cur != goal; cur = next[cur][goal]) と順番に辿れる.
public static int[][] warshallFloyd(long[][] adj){ // adj に全対最短路が入る.
    final int n = adj.length;

    int[][] next = new int[n][n];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            next[i][j] = j;
        }
    }

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(adj[i][j] < adj[i][k] + adj[k][j]){
                    adj[i][j] = adj[i][k] + adj[k][j];
                    next[i][j] = next[i][k];
                }
            }
        }
    }

    return next;
}

// WarshallFloyd して adj[i][j] != INF && adj[j][i] != INF なら同じ成分.
public static ArrayList<Set<Integer>> StrongConnectedComponents(long[][] adj){
    final int n = adj.length;

    long[][] wf_adj = warshallFloyd(adj);
    ArrayList<Set<Integer>> sets = new ArrayList<Set<Integer>>();
    for(int i = 0; i < n; i++){
        Set<Integer> set = new HashSet<Integer>();
        set.add(i);

        sets.add(set);
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(adj[i][j] != INF && adj[j][i] != INF){
                sets.get(i).add(j);
                sets.get(j).add(i);
            }
        }
    }

    return sets;
}

// adj -> 隣接行列, ts -> 木に含まれてほしい木
// 戻り値が INF以上なら, 要求を満たすシュタイナー木は存在しない.
public static long minimumSteinerTree(long[][] adj, int[] ts){
    final int n = adj.length;
    final int m = ts.length;

    // メモリが勿体無い場合は ワーシャルフロイドの結果を adj に入れる.
    long[][] all_pair = warshallFloyd(adj); //O(n^3)
    long[][] DP = new long[1 << m][n];

    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            DP[1 << i][j] = all_pair[ts[i]][j];
        }
    }

    for(int i = 1; i < (1 << m); i++){ // O(2^t)
        if(Integer.bitCount(i) == 1){ continue; } // ペア作れないのはNG

        for(int j = 0; j < n; j++){ // O(n)
            DP[i][j] = INF;
            // i と 0 以外の部分集合を列挙して, ペアで行ける場所の最小値を求める..
            for(int k = (i - 1) & i; k > 0; k = (k - 1) & i){
                DP[i][j] = Math.min(DP[i][j], DP[k][j] + DP[i ^ k][j]);
            } // DP[i][駅] は, iのシュタイナー木を作るコストが入る. (足し算してるから)
        }
        // このままだと, 辺を重複してカウントするので, ワーシャルして排除.
        for(int k = 0; k < n; k++) {
            for (int j = 0; j < n; j++) {
                DP[i][j] = Math.min(DP[i][j], DP[i][k] + all_pair[k][j]);
            }
        }
    }

    long ret = Long.MAX_VALUE;
    for(final int t : ts){ ret = Math.min(ret, DP[(1 << m) - 1][t]); }
    return ret;
}

// DFS で 前順走査(preorder) で 一番近い親を探す. 部分木のマージに, UnionFind を使う .
public static void dfs(int[] us, int[] vs, int[] lcas, int node, int parent,
                       boolean[] visited, int[] ancestor, boolean[][] adj, UnionFind uf){
    ancestor[uf.find(node)] = node; // 自分の祖先は自分.
    for(int next = 0; next < adj.length; next++){
        if(next == parent){ continue; }
        if(!adj[node][next]){ continue; }

        dfs(us, vs, lcas, next, node, visited, ancestor, adj, uf);
        uf.union(node, next); // next以下のLCAを探索し終えたので, 部分木を併合.
        ancestor[uf.find(node)] = node; // 併合した祖先は自分(部分木内はもう終えてる)
    }

    visited[node] = true;
    for(int i = 0; i < us.length; i++){
        int not_node = -1; // 片方が自分だった時のもう片方が欲しい
        if(us[i] == node){ not_node = vs[i]; }
        else if(vs[i] == node){ not_node = us[i]; }

        if(not_node >= 0 && visited[not_node]){ // 両方とも評価済みかのチェック
            lcas[i] = ancestor[uf.find(not_node)]; // 両方とも評価済みの場合は一度しかない.
        }
    }
}

//
public static int[] offlineLCA(int[] us, int[] vs, boolean[][] adj){
    final int n = adj.length;
    int[] lca_nodes = new int[us.length], ancestor = new int[n];
    boolean[] visited = new boolean[n];
    UnionFind uf = new UnionFind(n);

    dfs(us, vs, lca_nodes, 0, -1, visited, ancestor, adj, uf);
    return lca_nodes;
}

public static long minimumCut(final int n, long[][] adj){
    ArrayList<Integer> uf = new ArrayList<Integer>();
    for(int i = 0; i < n; i++){
        uf.add(i);
    }
    Set<Integer> set = new HashSet<Integer>(), ret = null;

    long cut = Long.MAX_VALUE;
    for(int m = n; m > 1; m--){
        long[] ws = new long[m];
        int u = 0, v = 0;
        long w = 0;

        for(int k = 0; k < m; k++){
            u = v;

            v = 0;
            {
                long tmp_max = ws[0];
                for(int i = 1; i < m; i++){
                    if(tmp_max < ws[i]){
                        tmp_max = ws[i];
                        v = i;
                    }
                }
            }

            w = ws[v];
            ws[v] = -1;

            for(int i = 0; i < m; i++){
                if(ws[i] >= 0){
                    ws[i] += adj[uf.get(v)][uf.get(i)];
                }
            }
        }

        for(int i = 0; i < m; i++){
            adj[uf.get(i)][uf.get(u)] += adj[uf.get(i)][uf.get(v)];
            adj[uf.get(u)][uf.get(i)] += adj[uf.get(v)][uf.get(i)];
        }

        set.add(uf.get(v));
        if(cut > w){
            cut = w;
            ret = new HashSet<Integer>(set);
        }

        uf.remove(v);
    }

    return cut;
}

public static long MinimumGeneralMatching(long[][] adj){
    final int n = adj.length;

    long[] DP = new long[1 << n];
    final int INF = Integer.MAX_VALUE / 2 - 1;

    for(int i = 0; i < 1 << n; i++){ DP[i] = INF; }
    DP[0] = 0;

    for(int bit = 0; bit < (1 << n); bit++){
        if(DP[bit] >= INF){ continue; }

        // 立ってない最初の bit だけ立ててて O(N) ループ節約
        int i = 0; for(; (bit & (1 << i)) != 0; i++);
        final int fst = 1 << i;

        for(int j = i + 1; j < n; j++){
            if((bit & (1 << j)) != 0){ continue; }

            final int snd = 1 << j;
            final int next_bit = bit | fst | snd;
            DP[next_bit] = Math.min(DP[next_bit], DP[bit] + adj[i][j]);
        }
    }

    return DP[(1 << n) - 1];
}

public static long gcd(long a, long b){
    return b == 0 ? a : gcd(b, a % b);
}
public static long lcm(long a, long b){
    return a / gcd(a, b) * b;
}

// 任意の Comparable<T> を実装したクラスに対する next_permutation
@SafeVarargs
public static <T extends Comparable<? super T>> boolean next_permutation(T ... perm) {
    for(int i = perm.length - 1; i > 0; i--){
        if(perm[i - 1].compareTo(perm[i]) < 0){
            int j = perm.length;
            while(perm[i - 1].compareTo(perm[--j]) >= 0);

            swap(perm, i - 1, j);
            reverse(perm, i, perm.length); // [i, n)

            return true;
        }
    }

    reverse(perm, 0, perm.length); // [0, n)
    return false;
}

// equalsメソッドは eclipse等で生成するなりして作ること
public static class Rational implements Comparable<Rational> {
    public static final Rational ZERO = new Rational(0);
    public static final Rational ONE  = new Rational(1);
    public static final Rational NaN  = new Rational(1, 0){
        public String toString(){ return "NaN"; }};

    private long nom, denom;

    public Rational(long nom, long denom) {
        if(nom == 0){ this.nom = 0; this.denom = 1; }
        else{ final long gcd = inner_gcd(nom, denom);
            this.nom = nom / gcd; this.denom = denom / gcd;
            if(this.nom * this.denom < 0){
                this.nom = -Math.abs(this.nom);
                this.denom = Math.abs(this.denom);
            }}}
    public Rational(long num) { this(num, 1); }
    public long get_nom(){ return this.nom; }
    public long get_denom(){ return this.denom; }
    private static long inner_gcd(long a, long b){
        return b == 0 ? a : inner_gcd(b, a % b); }
    private static long inner_lcm(long a, long b){
        return a / inner_gcd(a, b) * b; }
    public Rational minus(){ return new Rational(-this.nom, this.denom); }
    public Rational inv(){ return new Rational(this.denom, this.nom); }
    public long sign(){
        return this.nom ==0 ? 0 : inner_lcm(this.nom,this.denom) < 0 ?-1:1;}
    public Rational abs(){
        return new Rational(Math.abs(this.nom), Math.abs(this.denom));}

    public Rational add(Rational o){
        final long lcm = inner_lcm(this.denom, o.denom);
        return new Rational(lcm/this.denom*this.nom + lcm/o.denom*o.nom,lcm);}
    public Rational sub(Rational o){ return this.add(o.minus()); }
    public Rational mul(Rational o){ return new Rational(this.nom * o.nom, this.denom * o.denom); }
    public Rational div(Rational o){ return this.mul(o.inv()); }
    public Rational gcd(Rational o){
        return new Rational(inner_gcd(this.nom, o.nom), inner_lcm(this.denom, o.denom)); }
    public Rational lcm(Rational o){
        return new Rational(inner_lcm(this.nom, o.nom), inner_gcd(this.denom, o.denom)); }
    public Rational pow(long p){
        if(p == 0){ return Rational.ONE;
        }else if(p % 2 != 0){ return this.mul(pow(p - 1));
        }else{ Rational ret = pow(p / 2); return ret.mul(ret); }}

    @Override
    public int compareTo(Rational o){
        final long det = this.nom * o.denom - this.denom * o.nom;
        if(det < 0){ return -1;
        }else if(det > 0){ return 1;
        }else{ return 0; }}
}

// import java.math.BigInteger;
public static class BigRational implements Comparable<BigRational>{
    public static final BigRational ZERO = new BigRational(0, 1);
    public static final BigRational ONE  = new BigRational(1, 1);
    public static final BigRational NaN  = new BigRational(1, 0);

    public final BigInteger nom, denom;

    public BigRational(BigInteger nom, BigInteger denom){
        this.nom = calc_nom(nom,denom); this.denom = calc_denom(nom,denom); }

    public BigRational(BigInteger nom){ this(nom, BigInteger.valueOf(1)); }
    public BigRational(long nom, long denom){
        this(BigInteger.valueOf(nom), BigInteger.valueOf(denom)); }
    public BigRational(long nom){ this(nom, 1); }

    private static BigInteger inner_gcd(BigInteger a, BigInteger b){
        return b.equals(BigInteger.ZERO) ? a : inner_gcd(b, a.remainder(b));
    }
    private static BigInteger inner_lcm(BigInteger a, BigInteger b){
        return a.multiply(b).divide(a.gcd(b));}

    private static BigInteger calc_nom(BigInteger nom, BigInteger denom){
        nom = nom.divide(nom.gcd(denom));
        if(nom.signum() * denom.signum() < 0){ nom = nom.abs().negate(); }
        return nom; }
    private static BigInteger calc_denom(BigInteger nom, BigInteger denom){
        denom = denom.divide(nom.gcd(denom));
        if(nom.equals(BigInteger.ZERO)) { return BigInteger.ONE; }
        if(nom.signum() * denom.signum() < 0){ denom = denom.abs(); }
        return denom; }

    public BigRational minus(){ return new BigRational(nom.negate(), denom); }
    public BigRational inv()  { return new BigRational(denom, nom); }
    public int sign() { return nom.signum(); }
    public BigRational abs()  { return new BigRational(nom.abs(), denom); }
    public BigRational add(BigRational o)  {
        final BigInteger lcm = inner_lcm(this.denom, o.denom);
        return new BigRational(lcm.divide(this.denom).multiply(this.nom)
                .add(lcm.divide(o.denom).multiply(o.nom)), denom); }
    public BigRational sub(BigRational o){ return this.add(o.minus()); }
    public BigRational mul(BigRational o){
        return new BigRational(this.nom.multiply(o.nom), this.denom.multiply(o.denom)); }
    public BigRational div(BigRational o){ return this.mul(o.inv()); }
    public BigRational gcd(BigRational o){
        return new BigRational(inner_gcd(this.nom, o.nom), this.denom.divide(this.denom.gcd(o.denom)).multiply(o.denom)); }
    public BigRational lcm(BigRational o){
        return new BigRational(inner_lcm(this.nom, o.nom), this.denom.gcd(o.denom)); }
    public BigRational pow(int p){ return new BigRational(nom.pow(p), denom.pow(p)); }

    @Override
    public int compareTo(BigRational arg0){
        return this.nom.multiply(arg0.denom).compareTo(this.denom.multiply(arg0.nom)); }
}

public static long mod_pow(long a, long e, long m){
    if(e == 0){
        return 1;
    }else if(e % 2 == 0){
        long ret = mod_pow(a, e / 2, m);
        return (ret * ret) % m;
    }else{
        return (mod_pow(a, e - 1, m) * a) % m;
    }
}

public static long mod_pow(long a, long e, long m){
    long ret = 1;
    for(; e > 0; e /= 2){
        if (e % 2 != 0) ret = (ret * a) % m;
        a = (a * a) % m;
    }
    return ret;
}

public static long mod_inv(long a, long p){
    return mod_pow(a, p - 2, p);
}

// 返戻値(inv[1] ... inv[N]) にそれぞれの mod P での逆元が入る
public static long[] mod_inv(int N, long p){
    long[] inv = new long[N + 1];
    inv[1] = 1;
    for(int i = 2; i <= N; i++){
        inv[i] = p - (p / i) * inv[(int)(p % i)] % p;
    }
    return inv;
}

// a and m must be co-prime.
public static long mod_inv(long a, long m){
    return (a == 1 ? 1 : (1 - m*mod_inv(m%a, a)) / a + m);
}

//Gauss の方法で求める. 返り値の値の mod を取らないので O(N) くらい
public static long chinese_remainder(long[] as, long[] ms){
    long prod = 1;
    for(long m : ms){ prod *= m; }

    long ret = 0;
    for(int i = 0; i < ms.length; i++){
        final long M = prod / ms[i];
        final long inv = mod_inv(M % ms[i], ms[i]);

        long a = as[i] - as[i] / prod * prod;
        if(a < 0){ a += prod; }

        ret = (ret + M * inv * a % prod) % prod;
    }

    return ret;
}

// φ(n) = n (1 - 1/p1) ... (1 - 1/pm) (pkはnの素因数) より
// 初項から一つづつ展開する -> n -= n / pk を行う事になる.
public static long eulerPhiFunction(long n) {
    long phi = n;
    for(long p = 2; p * p <= n; p++){
        if(n % p == 0){
            phi -= phi / p;
            while(n % p == 0){ n /= p; }
        }
    }
    if(n > 1){ phi -= phi / n; }

    return phi;
}

//
public static long[] eulerPhiFunction(int n) { // [0, n]
    boolean[] is_prime = new boolean[n + 1];
    long[] phis = new long[n + 1];
    for(int i = 0; i <= n; i++){
        is_prime[i] = true;
        phis[i] = i;
    }
    is_prime[0] = is_prime[1] = false;

    for(int i = 2; i <= n; i++){
        if(is_prime[i]){
            phis[i] -= phis[i] / i;
            for(int j = i * 2; j <= n; j += i){
                is_prime[j] = false;    
                phis[j] -= phis[j] / i;
            }
        }
    }

    return phis;
}

// λ(2^k) = 1 (k == 1), 2 (k == 2), 2^(k - 2) (k >= 3)
// λ(p^k) = p^(k-1) * (p - 1) ... (p=奇素数の時)
// λ(p1^k1...pn^kn) = lcm(λ(p1^k1), ... λ(pn^kn))
public static long carmichaelLambdaFunction(long n) {
    long lambda = 1;
    if(n % 8 == 0){ n /= 2; } // 2^(k-2)になる時は, 先に2で割って奇素数(k-1乗)と同じにする.
    for(int p = 2; p <= n; p++){
        if(n % p == 0){
            long l = p - 1; // (p-1)部分を先に代入しとく. (2^k でも 1 になるので無問題)
            n /= p; while(n % p == 0){ n /= p; l *= p; } // (k-1)乗する.
            lambda = lcm(lambda, l);
        }
    }
    return lambda;
}

public static class Point2D {
    public double x;
    public double y;

    public static final double EPS = 1e-9;

    public Point2D(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public Point2D(Point2D point) {
        this.x = point.x;
        this.y = point.y;
    }

    public String toString() {
        return x + "," + y;
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof Point2D) {
            Point2D another = (Point2D) o;
            
            if(Point2D.eq(this.x, another.x) && Point2D.eq(this.y, another.y)){
                return true;
            }
            
            return false;
        }
        return false;
    }

    public Point2D add(double x, double y) {
        return new Point2D(this.x + x, this.y + y);
    }

    public Point2D sub(double x, double y) {
        return add(-x, -y);
    }

    public Point2D add(Point2D another) {
        return add(another.x, another.y);
    }

    public Point2D sub(Point2D another) {
        return sub(another.x, another.y);
    }

    public Point2D mul(double d) {
        return new Point2D(this.x * d, this.y * d);
    }

    public Point2D div(double d) {
        return new Point2D(this.x / d, this.y / d);
    }

    public double dot(double x, double y) {
        return this.x * x + this.y * y;
    }

    public double dot(Point2D another) {
        return dot(another.x, another.y);
    }

    public double cross(double x, double y) {
        return this.x * y - this.y * x;
    }

    public double cross(Point2D another) {
        return cross(another.x, another.y);
    }

    public double dist(double x, double y) {
        return Math.sqrt((this.x - x) * (this.x - x) + (this.y - y)
                * (this.y - y));
    }

    public double dist(Point2D another) {
        return dist(another.x, another.y);
    }

    public double dist_o() {
        return dist(0, 0);
    }

    public Point2D unit() {
        return div(dist_o());
    }

    public boolean pol(Point2D start, Point2D end) {
        return end.sub(start).cross(this.sub(start)) < EPS;
    }

    public boolean pos(Point2D start, Point2D end) {
        return (start.dist(this) + this.dist(end) < start.dist(end) + EPS);
    }

    public double pld(Point2D start, Point2D end) {
        return Math.abs((end.sub(start).cross(this.sub(start)))
                / end.sub(start).dist_o());
    }

    public double psd(Point2D start, Point2D end) {
        if (end.sub(start).dot(this.sub(start)) < EPS) {
            return this.dist(start);
        } else if (start.sub(end).dot(this.sub(end)) < EPS) {
            return this.dist(end);
        } else {
            return Math.abs(end.sub(start).cross(this.sub(start)) / end.dist(start));
        }
    }
    
    public static int signum(double x){
        return Math.abs(x) < EPS ? 0 : x > 0 ? 1 : -1;
    }
    
    public static boolean eq(double x, double y){
        return signum(x - y) == 0;
    }
    
    public static int ccw(Point2D p, Point2D r, Point2D s){
        Point2D a = r.sub(p);
        Point2D b = s.sub(p);
        
        final int sgn = Point2D.signum(a.cross(b));
        if(sgn != 0){
            return sgn;
        }else if(a.x * b.x < -EPS && a.y * b.y < -EPS){
            return -1;
        }else if(a.dist_o() < b.dist_o() - EPS){
            return 1;
        }else{
            return 0;
        }
    }
    
    public static boolean intersect_s(Point2D a1, Point2D a2, Point2D b1,
            Point2D b2) {
        return (Point2D.ccw(a1, a2, b1) * Point2D.ccw(a1, a2, b2) <= 0)
                && (Point2D.ccw(b1, b2, a1) * Point2D.ccw(b1, b2, a2) <= 0);
    }

    public static boolean insersect_l(Point2D a1, Point2D a2, Point2D b1,
            Point2D b2) {
        return a1.sub(a2).cross(b1.sub(b2)) < EPS;
    }

    public static Point2D interpoint_s(Point2D a1, Point2D a2, Point2D b1,
            Point2D b2) {
        Point2D b = b2.sub(b1);
        double d1 = Math.abs(b.cross(a1.sub(b1)));
        double d2 = Math.abs(b.cross(a2.sub(b1)));
        double t = d1 / (d1 + d2);
        Point2D a = a2.sub(a1), v = a.mul(t);
        return a1.add(v);
    }

    public static Point2D interpoint_l(Point2D a1, Point2D a2, Point2D b1,
            Point2D b2) {
        Point2D a = a2.sub(a1);
        Point2D b = b2.sub(b1);
        double t = b.cross(b1.sub(a1)) / b.cross(a);
        Point2D v = a.mul(t);
        return a1.add(v);
    }

    public static Point2D[] cross_ss(Point2D p1, double r1, Point2D p2,
            double r2) {
        double dis = p1.dist(p2);

        if (r1 + EPS > r2 && r1 - EPS < r2 && dis < EPS) {
            return new Point2D[0]; // same
        }

        if (dis - EPS < r1 + r2 && dis + EPS > r1 + r2) {
            Point2D tmp = p2.sub(p1);
            tmp = tmp.mul(r1 / tmp.dist_o());
            Point2D ret[] = new Point2D[1];
            ret[0] = p1.add(tmp);
            return ret;
        } else if (dis + EPS > r1 + r2) {
            return new Point2D[0]; // out
        }

        double dis_m = Math.abs(r1 - r2);

        if (dis_m + EPS > dis && dis_m - EPS < dis) {
            Point2D tmp = null;
            if (r1 > r2) {
                tmp = p2.sub(p1);
            } else {
                tmp = p1.sub(p2);
            }

            double min = Math.min(r1, r2);

            tmp = tmp.mul((min + tmp.dist_o()) / tmp.dist_o());

            Point2D ret[] = new Point2D[1];
            ret[0] = p1.add(tmp);
            return ret;
        } else if (dis_m + EPS > dis) {
            return new Point2D[0]; // inner
        } else {
            Point2D ret[] = new Point2D[2];

            double theta = Math.acos((dis * dis + r1 * r1 - r2 * r2)
                    / (2 * dis * r1));
            double a = Math.atan2(p2.y - p1.y, p2.x - p1.x);

            ret[0] = new Point2D(r1 * Math.cos(a + theta) + p1.x, r1
                    * Math.sin(a + theta) + p1.y);
            ret[1] = new Point2D(r1 * Math.cos(a - theta) + p1.x, r1
                    * Math.sin(a - theta) + p1.y);
            return ret;
        }
    }
    
    public static double ss_dist(Point2D start1, Point2D end1, Point2D start2, Point2D end2){
        if(Point2D.intersect_s(start1, end1, start2, end2)){
            return 0;
        }else{
            return Math.min(Math.min(Math.min(start1.psd(start2, end2), end1.psd(start2, end2)), start2.psd(start1, end1)), end2.psd(start1, end1));
        }
    }
    
    public void interpoint_lc(Point2D start, Point2D end, Point2D c, double r,
            Point2D ans[]) {
        if (c.pld(start, end) > r + EPS)
            return;
        Point2D v = end.sub(start).unit();
        double delta = v.dot(start.sub(c)) * v.dot(start.sub(c))
                - start.dist(c) * start.dist(c) + r * r;
        double t = -v.dot(start.sub(c));
        double s = Math.sqrt(delta);
        ans[0] = start.add(v.mul(t + s));
        ans[1] = start.add(v.mul(t + s));
    }

    public Point2D normal_vector(Point2D p, Point2D a, Point2D b) {
        Point2D v = b.sub(a).unit();
        v = v.cross(p.sub(a)) > 0 ? new Point2D(v.y, (-1) * v.x) : new Point2D(
                (-1) * v.y, v.x);
        return v.mul(p.pld(a, b));
    }

    public double area(Point2D a, Point2D b, Point2D c) {
        return Math.abs((c.sub(a).cross(b.sub(a))) * 0.5);
    }
}

public static class Point2D implements Comparable<Point2D>{
    public static final Point2D NaN = new Point2D(Rational.NaN, Rational.NaN);
    
    private Rational x, y;
    
    public Point2D(Rational x, Rational y){
        assert(x != null && y != null); // nullを入れたら殺す!
        this.x = x; this.y = y;
    }
    
    public Rational get_x(){ return x; }
    public Rational get_y(){ return y; }
    public Rational norm(){ return this.x.pow(2).add(this.y.pow(2)); }
    
    public Point2D add(Point2D o){return new Point2D(x.add(o.x),y.add(o.y)); }
    public Point2D sub(Point2D o){return new Point2D(x.sub(o.x),y.sub(o.y)); }
    public Point2D mul(Rational r){ return new Point2D(x.mul(r), y.mul(r)); }
    public Point2D div(Rational r){ return new Point2D(x.div(r), y.div(r)); }
    
    public Rational dot(Point2D o)  { return x.mul(o.x).add(y.mul(o.y)); }
    public Rational cross(Point2D o){ return x.mul(o.y).sub(y.mul(o.x)); }
    public Rational dist(Point2D o) { return o.sub(this).norm(); }
    
    public long ccw(Point2D r, Point2D s){
        final Point2D a = r.sub(this), b = s.sub(this);
        final long sign = a.cross(b).sign();
        
        if(sign != 0){ return sign;
        }else if(a.x.mul(b.x).sign() < 0 || a.y.mul(b.y).sign() < 0){
            return -1;
        }else if(a.norm().compareTo(b.norm()) < 0){
            return 1;
        }else{ return 0; }
    }
    
    @Override
    public boolean equals(Object obj) { //必要ならHashCodeも生成する事
        if(!(obj instanceof Point2D)){ return false; }
        Point2D o = (Point2D) obj;
        if(!this.x.equals(o.x) || !this.y.equals(o.y)){ return false; }
        return true;
    }

    @Override
    public int compareTo(Point2D o) {
        if(this.x.compareTo(o.x) != 0){ return this.x.compareTo(o.x); }
        else if(this.y.compareTo(o.y) != 0){ return this.y.compareTo(o.y); }
        else { return 0; }
    }
}

public static class Point2D implements Comparable<Point2D>{
    public static final Point2D NaN = new Point2D(Rational.NaN, Rational.NaN);
    
    private Rational x, y;
    
    public Point2D(Rational x, Rational y){
        assert(x != null && y != null); // nullを入れたら殺す!
        this.x = x; this.y = y;
    }
    
    public Rational get_x(){ return x; }
    public Rational get_y(){ return y; }
    public Rational norm(){ return this.x.pow(2).add(this.y.pow(2)); }
    
    public Point2D add(Point2D o){return new Point2D(x.add(o.x),y.add(o.y)); }
    public Point2D sub(Point2D o){return new Point2D(x.sub(o.x),y.sub(o.y)); }
    public Point2D mul(Rational r){ return new Point2D(x.mul(r), y.mul(r)); }
    public Point2D div(Rational r){ return new Point2D(x.div(r), y.div(r)); }
    
    public Rational dot(Point2D o)  { return x.mul(o.x).add(y.mul(o.y)); }
    public Rational cross(Point2D o){ return x.mul(o.y).sub(y.mul(o.x)); }
    public Rational dist(Point2D o) { return o.sub(this).norm(); }
    
    public long ccw(Point2D r, Point2D s){
        final Point2D a = r.sub(this), b = s.sub(this);
        final long sign = a.cross(b).sign();
        
        if(sign != 0){ return sign;
        }else if(a.x.mul(b.x).sign() < 0 || a.y.mul(b.y).sign() < 0){
            return -1;
        }else if(a.norm().compareTo(b.norm()) < 0){
            return 1;
        }else{ return 0; }
    }
    
    @Override
    public boolean equals(Object obj) { //必要ならHashCodeも生成する事
        if(!(obj instanceof Point2D)){ return false; }
        Point2D o = (Point2D) obj;
        if(!this.x.equals(o.x) || !this.y.equals(o.y)){ return false; }
        return true;
    }

    @Override
    public int compareTo(Point2D o) {
        if(this.x.compareTo(o.x) != 0){ return this.x.compareTo(o.x); }
        else if(this.y.compareTo(o.y) != 0){ return this.y.compareTo(o.y); }
        else { return 0; }
    }
}

//Mのbit幅 >= パターンの文字列じゃないと死ぬ. 長いならBitSetを使おう.
public static int shift_and(String t, String p){ //pの長さはbit幅依存
    int[] M = new int[Character.MAX_VALUE]; // alphabet全体分の長さが必要. 
    int count = 0;
    for(int i = 0; i < p.length(); i++){
        M[p.charAt(i)] |= (1 << i);
    }
    
    for(int i = 0, S = 0; i < t.length(); i++){
        S = ((S << 1) | 1) & M[t.charAt(i)];
        
        if((S & (1 << (p.length() - 1))) != 0){
            count++; // t[i - p.length() + 1, i] 
        }
    }
    
    return count;
}

public static long rolling_hash(String s, final long b, final long m){
    long ret = 0l;
    for(char c : s.toCharArray()){
        ret *= b; ret %= m;
        ret += c; ret %= m;
    }
    return ret;
}

// 0枚で終わると負け(最後の一枚を取った人が勝ちの場合)
public static boolean Nim(long ... nim) {
    long ret = 0;
    for(final long n : nim){ ret ^= n; }

    return ret != 0;
}

public static class Dice {
    public static int MAX = 5, SIZE = 7;
    public static int TOP = 0, FRONT = 1, RIGHT = 2;
    public static int BOTTOM = 5, BACK = 4, LEFT = 3;

    int[] dice; // in [1, 2, 3, 4, 5, 6]

    public Dice(int top, int front, int right, int sum) {
        dice = new int[MAX + 1];
        dice[TOP] = top; dice[FRONT] = front; dice[RIGHT] = right;
        dice[BOTTOM] = sum - top; dice[BACK] = sum - front; dice[LEFT] = sum - right;
    }

    public Dice(int top, int front, int right) {
        this(top, front, right, SIZE);
    }

    // rotate_from は (top | front) から見てどの方向に転がるを指定すると転がしてくれる.
    public void rotate_from_top(final int dir) { rotate_dice(TOP, dir, BOTTOM, MAX - dir); }
    public void rotate_from_front(final int dir){ rotate_dice(FRONT, dir, BACK, MAX - dir); }

    public void rotate_dice(int... args) {
        final int tmp = dice[args[args.length - 1]];
        for (int now = args.length - 1; now > 0; now--) {
            dice[args[now]] = dice[args[now - 1]];
        }

        dice[args[0]] = tmp;
    }
}