You are given a rooted tree. Each vertex contains a_i tons of gold, which costs c_i per one ton. Initially, the tree consists only a root numbered 0 with a_0 tons of gold and price c_0 per ton.

There are q queries. Each query has one of two types: 

  1. Add vertex i (where i is an index of query) as a son to some vertex p_i; vertex i will have a_i tons of gold with c_i per ton. It's guaranteed that c_i > c_{p_i}. 
  2. For a given vertex v_i consider the simple path from v_i to the root. We need to purchase w_i tons of gold from vertices on this path, spending the minimum amount of money. If there isn't enough gold on the path, we buy all we can. 



If we buy x tons of gold in some vertex v the remaining amount of gold in it decreases by x (of course, we can't buy more gold that vertex has at the moment). For each query of the second type, calculate the resulting amount of gold we bought and the amount of money we should spend.

Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query, so don't forget to flush output after printing answers. You can use functions like fflush(stdout) in C++ and BufferedWriter.flush in Java or similar after each writing in your program. In standard (if you don't tweak I/O), endl flushes cout in C++ and System.out.println in Java (or println in Kotlin) makes automatic flush as well. 

Input

The first line contains three integers q, a_0 and c_0 (1 ≤ q ≤ 3 ⋅ 10^5; 1 ≤ a_0, c_0 < 10^6) — the number of queries, the amount of gold in the root and its price.

Next q lines contain descriptions of queries; The i-th query has one of two types: 

  * "1 p_i a_i c_i" (0 ≤ p_i < i; 1 ≤ a_i, c_i < 10^6): add vertex i as a son to vertex p_i. The vertex i will have a_i tons of gold with price c_i per one ton. It's guaranteed that p_i exists and c_i > c_{p_i}.
  * "2 v_i w_i" (0 ≤ v_i < i; 1 ≤ w_i < 10^6): buy w_i tons of gold from vertices on path from v_i to 0 spending the minimum amount of money. If there isn't enough gold, we buy as much as we can. It's guaranteed that vertex v_i exist. 



It's guaranteed that there is at least one query of the second type.

Output

For each query of the second type, print the resulting amount of gold we bought and the minimum amount of money we should spend.

Example

Input


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


Output


2 4
4 10
1 3

Note

Explanation of the sample:

At the first query, the tree consist of root, so we purchase 2 tons of gold and pay 2 ⋅ 2 = 4. 3 tons remain in the root.

At the second query, we add vertex 2 as a son of vertex 0. Vertex 2 now has 3 tons of gold with price 4 per one ton.

At the third query, a path from 2 to 0 consists of only vertices 0 and 2 and since c_0 < c_2 we buy 3 remaining tons of gold in vertex 0 and 1 ton in vertex 2. So we bought 3 + 1 = 4 tons and paid 3 ⋅ 2 + 1 ⋅ 4 = 10. Now, in vertex 0 no gold left and 2 tons of gold remain in vertex 2.

At the fourth query, we add vertex 4 as a son of vertex 0. Vertex 4 now has 1 ton of gold with price 3.

At the fifth query, a path from 4 to 0 consists of only vertices 0 and 4. But since no gold left in vertex 0 and only 1 ton is in vertex 4, we buy 1 ton of gold in vertex 4 and spend 1 ⋅ 3 = 3. Now, in vertex 4 no gold left.
import java.io.*;
import java.text.DecimalFormat;
import java.util.*;

public class Main {
    public static final DecimalFormat DF_2 = new DecimalFormat("0.000");

    public static void main(String[] args) throws IOException {
        long startTime = System.currentTimeMillis();

//          InputReader in = new InputReader(new FileInputStream("input.txt"));
        //  PrintWriter out = new PrintWriter(new BufferedOutputStream(new FileOutputStream("boards.out")));

        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

        int q = readInt();
        List<Integer>[] paths = new ArrayList[q + 1];
        paths[0] = new ArrayList<>();
        long[] cnt = new long[q + 1];
        long[] costs = new long[q + 1];
        cnt[0] = readInt();
        costs[0] = readInt();

        for (int i = 0; i < q; i++) {
            int t = readInt();
            if (t == 1) {
                int p = readInt();
                cnt[i + 1] = readInt();
                costs[i + 1] = readInt();

                ArrayList<Integer> path = new ArrayList<>();
                int pp = p;
                int d = 0;
                while (true) {
                    path.add(pp);
                    if (d < paths[pp].size()) {
                        pp = paths[pp].get(d);
                    } else {
                        break;
                    }
                    d += 1;
                }

                paths[i + 1] = path;
            } else {
                int v = readInt();
                int w = readInt();

                long taken = 0;
                long cost = 0;
                while (w > 0 && cnt[v] > 0) {
                    int u = v;
                    for (int j = paths[u].size() - 1; j >= 0; j--) {
                        if (cnt[paths[u].get(j)] > 0) {
                            u = paths[u].get(j);
                            j = Math.min(j, paths[u].size());
                        }
                    }

                    long take = Math.min(w, cnt[u]);
                    if (take <= 0) {
                        break;
                    }
                    cnt[u] -= take;
                    taken += take;
                    cost += costs[u] * take;
                    w -= take;
                }
                out.println(taken + " " + cost);
                out.flush();
            }

        }

        out.flush();
        out.close();
    }

    private static int readInt() throws IOException {
        int ret = 0;
        boolean dig = false;
        for (int c = 0; (c = System.in.read()) != -1; ) {
            if (c >= '0' && c <= '9') {
                dig = true;
                ret = ret * 10 + c - '0';
            } else if (dig) break;
        }
        return ret;
    }

    private static void outputArray(int[] ans, PrintWriter out, boolean addOne) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            long an = ans[i] + (addOne ? 1 : 0);
            str.append(an);
            if (i < ans.length - 1) {
                str.append(" ");
            }
        }
        out.println(str);
    }

    private static long fromBinary(int[] binary) {
        long res = 0;
        long d = 1;
        for (int i = 0; i < binary.length; i++) {
            if (binary[i] == 1) {
                res = res | d;
            }
            d = d << 1;
        }
        return res;
    }

    private static int[] getBinary(long a, int size) {
        int[] result = new int[size];
        for (int i = 0; i < size; i++) {
            result[i] = (int) ((a >> i) & 1);
        }
        return result;
    }


    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextString() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }

        public String nextWord() {
            return next();
        }

        private List<Integer>[] readTree(int n) {
            return readGraph(n, n - 1);
        }

        private List<Integer>[] readGraph(int n, int m) {
            List<Integer>[] result = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                result[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                result[u].add(v);
                result[v].add(u);
            }
            return result;
        }

        private Map<Integer, Integer>[] readWeightedGraph(int n, int m, List<int[]> edges) {
            Map<Integer, Integer>[] result = new HashMap[n];
            for (int i = 0; i < n; i++) {
                result[i] = new HashMap<>();
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                int w = nextInt();
                result[u].put(v, w);
                result[v].put(u, w);
                edges.add(new int[]{w, v, u});
            }
            return result;
        }

    }
}