Problem: You are given a functional graph. It is a directed graph, in which from each vertex goes exactly one arc. The vertices are numerated from 0 to n - 1.

Graph is given as the array f0, f1, ..., fn - 1, where fi — the number of vertex to which goes the only arc from the vertex i. Besides you are given array with weights of the arcs w0, w1, ..., wn - 1, where wi — the arc weight from i to fi.

<image> The graph from the first sample test.

Also you are given the integer k (the length of the path) and you need to find for each vertex two numbers si and mi, where:

  * si — the sum of the weights of all arcs of the path with length equals to k which starts from the vertex i; 
  * mi — the minimal weight from all arcs on the path with length k which starts from the vertex i. 



The length of the path is the number of arcs on this path.

Input

The first line contains two integers n, k (1 ≤ n ≤ 105, 1 ≤ k ≤ 1010). The second line contains the sequence f0, f1, ..., fn - 1 (0 ≤ fi < n) and the third — the sequence w0, w1, ..., wn - 1 (0 ≤ wi ≤ 108).

Output

Print n lines, the pair of integers si, mi in each line.

Examples

Input

7 3
1 2 3 4 3 2 6
6 3 1 4 2 2 3


Output

10 1
8 1
7 1
10 2
8 2
7 1
9 3


Input

4 4
0 1 2 3
0 1 2 3


Output

0 0
4 1
8 2
12 3


Input

5 3
1 2 3 4 0
4 1 2 14 3


Output

7 1
17 1
19 2
21 3
8 1

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
public class FunctionalG{
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.flush();out.close();
    }
        static class TaskE {
            class pair{
                long F, S; 
                pair(long a, long b){F = a; S = b;}
            }
            final long gmax = Integer.MAX_VALUE;
            int n ; long k;
            int maxn;
            int ja[][] ,c[] , from[], to[]; long w[];
            ArrayList<Integer> map[];
           public void solve(int testNumber, InputReader in, PrintWriter out) {
{            
            n = in.nextInt(); k = in.nextLong();
            maxn = n + 10;
            ja = new int[maxn][]; c = new int[maxn];
            from  = new int[maxn]; to = new int[maxn];
            w = new long[maxn];
            map = new ArrayList[maxn];
            for(int i = 0; i < maxn; i++)map[i] = new ArrayList<>();

            for(int i = 1; i <= n; i++){
                from[i] = i; to[i]= in.nextInt() + 1;
                map[to[i]].add(from[i]);
                c[from[i]]++; c[to[i]]++;
            }

            for(int i = 1; i < maxn; i++){
                ja[i] = new int[c[i]]; c[i] = 0;
            }

            for(int i = 1; i <= n; i++){
                ja[from[i]][c[from[i]]++] = to[i];
                ja[to[i]][c[to[i]]++] = -from[i];
            }

            for(int i = 1; i <= n; i++){
                w[i] = in.nextLong();
            }

            visit = new int[maxn]; 
            for(int i = 1; i <= n; i++){
                if(visit[i] == 0){
                    scc(i , false, null);
                }
            }
            o : while(!ad.isEmpty()){
                int u = ad.pollFirst();
                while(visit[u] == 2){
                    if(ad.isEmpty())break o;
                    u = ad.pollFirst();
                }
                ArrayList<Integer> pal = new ArrayList<>();
                scc(u, true, pal);
                if(pal.size() > 1){
                    al.add(pal);
                }
            }
            
            s = new long[maxn]; m = new long[maxn];
            id = new int[maxn]; loop = new int[maxn];
            inc = new boolean[maxn];
            mval = new long[maxn][20]; parent = new int[maxn][20];

            for(int j = 1; j <= n; j++)Arrays.fill(mval[j], gmax);

            sum = new long[maxn][20]; d = new int[maxn];
            seg = new long[al.size()][][][];
}

            for(int i = 0; i < al.size(); i++){
                ArrayList<Integer> p = al.get(i);
                // System.out.println(p);
                int sz = p.size();
                seg[i] = new long[sz][20][2];

                for(int j = 0; j < sz; j++){
                    //0 -> min
                    seg[i][j][0][0] = seg[i][j][0][1] = w[p.get(j)];
                    for(int k = 1; k < 20; k++)seg[i][j][k][0] = gmax;
                }
                for(int k = 1; k < 20; k++){
                    for(int j = 0; j < sz; j++){
                        int pa = j + (1 << (k - 1));
                        long ps[] = seg[i][j][k], ps1[] = seg[i][j][k - 1], 
                        ps2[] = pa >= sz ? new long[]{gmax, 0} : seg[i][pa][k - 1];
                        ps[0] = Math.min(ps1[0], ps2[0]);
                        ps[1] = ps1[1] + ps2[1];
                    }
                }
                for(int j = 0; j < p.size(); j++){
                    upd(p , i, j, k, false);
                }
                for(int j = 0; j < p.size(); j++){
                    int x = p.get(j);
                    dfs(x , 0);
                }
            }

            for(int i = 1; i <= n; i++){
                if(to[i] == i){
                    inc[i] = true;
                    dfs(i , 0);
                }
            }

            for(int i = 1; i < 20; i++){
                for(int j = 1; j <= n; j++){
                    int pa = parent[j][i - 1];
                    long a = mval[j][i - 1], b = sum[j][i - 1]; 
                    if(pa == 0){
                        a = gmax; b = 0;
                    }
                    parent[j][i] = parent[parent[j][i - 1]][i - 1];
                    mval[j][i] = Math.min(mval[pa][i - 1], a);
                    sum[j][i] = sum[pa][i - 1] + b;
                }
            }

            for(int i = 1; i <= n; i++){
                if(to[i] == i){
                    m[i] = w[i]; s[i] = k * w[i];
                    continue;
                }
                if(inc[i])continue;
                long y = Math.min(k , d[i]);
                m[i] = gmax;
                int pn = i;
                for(int j = 19; j >= 0 && y > 0; j--){
                    if((y >> j) != 0){
                        // System.out.println(i + " " + pn + " " + y + " " + j + mval[pn][j]);
                        m[i] = Math.min(m[i] , mval[pn][j]);
                        s[i] += sum[pn][j];
                        pn = parent[pn][j];
                        y -= (1 << j);
                    }
                }
                if(k > d[i]){
                    pair pp;
                    if(to[pn] == pn){
                        pp = new pair(w[pn], (k - d[i]) * w[pn]);
                    }else pp = upd(al.get(loop[pn]), loop[pn], id[pn], k - d[i], true);
                    m[i] = Math.min(m[i], pp.F); s[i] += pp.S;
                }
            }

            for(int i = 1; i <= n; i++){
                out.println(s[i] + " " + m[i]);
            }
          }
        boolean inc[];

        pair upd(ArrayList<Integer> p, int i , int j, long k, boolean t){
            int sz = p.size();
            int x = p.get(j);
            if(!t){inc[x] = true; id[x] = j; loop[x] = i;}
            long a = k / sz ; int b = (int)(k % sz);
            long min;
            long v1 = query(i , 0 , sz - 1);
            int y = sz - j;
            int z = Math.min(b, y);
            long v2 = query(i , j, j + z - 1) + query(i , 0, b - z - 1);
            if(a > 0){
                min = get(i , 0, sz - 1);
            }else{
                min = Math.min(get(i , j , j + z - 1), get(i , 0 , b -z - 1));
            }
            if(!t){s[x] = v1 * a + v2; m[x] = min; return null;}
            return new pair(min , v1 * a + v2);
        }

        long query(int id, int l, int r){
            int len = r - l + 1;
            long sum = 0;
            for(int i = 19; i >= 0 && r - l + 1 > 0; i--){
                if((len >> i) != 0){
                    sum += seg[id][l][i][1];
                    l += (1 << i);
                    len = r - l + 1;
                }
            }
            return sum;
        }

        long get(int id, int l, int r){
            int len = r - l + 1;
            long min = gmax;
            for(int i = 19; i >= 0 && r - l + 1 > 0; i--){
                if((len >> i) != 0){
                    min = Math.min(min , seg[id][l][i][0]);
                    l += (1 << i);
                    len = r - l + 1;
                }
            }
            return min;
        }

        long mval[][], sum[][], seg[][][][];
        int parent[][], d[];

        void dfs(int u, int pa){
            for(int v : ja[u]){
                int v1 = Math.abs(v);
                if(v < 0 && !inc[v1]){
                    mval[v1][0] = w[v1];
                    sum[v1][0] = w[v1];
                    parent[v1][0] = u;
                    d[v1] = d[u] + 1;
                    dfs(v1, u);
                }
            }
        }

        ArrayDeque<Integer> ad = new ArrayDeque<>();
        ArrayList<ArrayList<Integer>> al = new ArrayList<>();
        ArrayList<Integer> pal = new ArrayList<>();

        int id[], loop[];
        int visit[];
        long s[], m[];
        void scc(int u, boolean rev, ArrayList<Integer> pal){
            visit[u] = rev ? 2 : 1;
            for(int v : ja[u]){
                int v1 = Math.abs(v);
                if((v > 0 && (rev || visit[v] == 1)) || (v < 0 && (!rev || visit[v1] == 2)))continue;
                scc(v1, rev, pal);
            }
            if(rev){pal.add(u);}
            if(!rev)ad.addFirst(u);
        }

    }
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}