Problem: Barney is searching for his dream girl. He lives in NYC. NYC has n junctions numbered from 1 to n and n - 1 roads connecting them. We will consider the NYC as a rooted tree with root being junction 1. m girls live in NYC, i-th of them lives along junction ci and her weight initially equals i pounds.

<image>

Barney consider a girl x to be better than a girl y if and only if: girl x has weight strictly less than girl y or girl x and girl y have equal weights and index of girl x living junction index is strictly less than girl y living junction index, i.e. cx < cy. Thus for any two girls one of them is always better than another one.

For the next q days, one event happens each day. There are two types of events:

  1. Barney goes from junction v to junction u. As a result he picks at most k best girls he still have not invited from junctions on his way and invites them to his house to test if one of them is his dream girl. If there are less than k not invited girls on his path, he invites all of them.
  2. Girls living along junctions in subtree of junction v (including v itself) put on some weight. As result, their weights increase by k pounds. 



Your task is for each event of first type tell Barney the indices of girls he will invite to his home in this event.

Input

The first line of input contains three integers n, m and q (1 ≤ n, m, q ≤ 105) — the number of junctions in NYC, the number of girls living in NYC and the number of events respectively.

The next n - 1 lines describes the roads. Each line contains two integers v and u (1 ≤ v, u ≤ n, v ≠ u) meaning that there is a road connecting junctions v and u .

The next line contains m integers c1, c2, ..., cm (1 ≤ ci ≤ n) — the girl's living junctions.

The next q lines describe the events in chronological order. Each line starts with an integer t (1 ≤ t ≤ 2) — type of the event .

If t = 1 then the line describes event of first type three integers v, u and k (1 ≤ v, u, k ≤ n) follow — the endpoints of Barney's path and the number of girls that he will invite at most.

Otherwise the line describes event of second type and two integers v and k (1 ≤ v ≤ n, 1 ≤ k ≤ 109) follow — the root of the subtree and value by which all the girls' weights in the subtree should increase.

Output

For each event of the first type, print number t and then t integers g1, g2, ..., gt in one line, meaning that in this event Barney will invite t girls whose indices are g1, ..., gt in the order from the best to the worst according to Barney's considerations.

Example

Input

5 7 11
3 5
2 3
4 3
1 4
4 1 4 5 4 1 4
2 4 3
1 2 1 2
1 4 2 1
2 2 10
2 1 10
1 2 4 1
1 2 3 4
2 5 2
2 4 9
1 3 5 2
1 1 2 3


Output

2 2 1 
1 3 
1 5 
0 
1 4 
2 6 7 

Note

For the first sample case:

<image>

Description of events:

  1. Weights of girls in subtree of junction 4 increase by 3. These girls have IDs: 1, 3, 5, 4, 7. 
  2. Barney goes from junction 2 to 1. Girls on his way have IDs 1, 2, 3, 5, 6, 7 with weights 4, 2, 6, 8, 6, 10 respectively. So, he invites girls 2 and 1. 
  3. Barney goes from junction 4 to junction 2. Girls on his way has IDs 3, 5, 7 with weights 6, 8, 10 respectively. So he invites girl 3. 
  4. Weight of girls in subtree of junction 2 increase by 10. There are no not invited girls, so nothing happens. 
  5. Weight of girls in subtree of junction 1 increase by 10. These girls (all girls left) have IDs: 4, 5, 6, 7. 
  6. Barney goes from junction 2 to junction 4. Girls on his way has IDs 5, 7 with weights 18, 20 respectively. So he invites girl 5. 
  7. Barney goes from junction 2 to junction 3. There is no girl on his way. 
  8. Weight of girls in subtree of junction 5 increase by 2. The only girl there is girl with ID 4. 
  9. Weight of girls in subtree of junction 4 increase by 9. These girls have IDs: 4, 6, 7. 
  10. Barney goes from junction 3 to junction 5. Only girl on his way is girl with ID 4. 
  11. Barney goes from junction 1 to junction 2. Girls on his way has IDs 6, 7 with weights 16, 29 respectively. 

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.function.LongBinaryOperator;
import java.util.PriorityQueue;
import java.util.AbstractQueue;
import java.util.ArrayList;
import java.util.AbstractCollection;
import java.io.OutputStreamWriter;
import java.util.function.IntFunction;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.List;
import java.io.Closeable;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            EWaitForIt solver = new EWaitForIt();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class EWaitForIt {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int m = in.readInt();
            int q = in.readInt();

            HeavyLightDecompose dec = new HeavyLightDecompose(Math::max, n, 0);
            for (int i = 0; i < n - 1; i++) {
                int u = in.readInt() - 1;
                int v = in.readInt() - 1;
                dec.addEdge(u, v);
            }

            long inf = (long) 1e18;

            int[] belong = new int[m];
            QueryObject qo = new QueryObject();
            for (int i = 0; i < m; i++) {
                int u = in.readInt() - 1;
                belong[i] = u;
                dec.setInitVal(u, i + 1);
            }
            dec.finish();

            IntegerArrayList list = new IntegerArrayList(n);
            for (int i = 0; i < q; i++) {
                int t = in.readInt();
                if (t == 1) {
                    int u = in.readInt() - 1;
                    int v = in.readInt() - 1;
                    int k = in.readInt();

                    list.clear();
                    while (k > 0) {
                        qo.reset();
                        dec.processPath(u, v, qo);
                        if (qo.val >= inf) {
                            break;
                        }
                        k--;
                        list.add(qo.index + 1);
                        dec.pop(belong[qo.index]);
                    }
                    out.println(list.size());
                    for (int j = 0; j < list.size(); j++) {
                        out.append(list.get(j)).append(' ');
                    }
                    out.println();
                } else {
                    int v = in.readInt() - 1;
                    int k = in.readInt();
                    dec.updateSubtree(v, k);
                }
            }


        }

    }

    static class HeavyLightDecompose {
        private LongBinaryOperator op;
        int n;
        int order = 1;
        HeavyLightDecompose.HLDNode root;
        HeavyLightDecompose.HLDNode[] nodes;
        HeavyLightDecompose.HLDNode[] segIndexToNode;
        HeavyLightDecompose.Segment segment;

        public HeavyLightDecompose(LongBinaryOperator op, int n, int rootId) {
            this.op = op;
            this.n = n;
            nodes = new HeavyLightDecompose.HLDNode[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new HeavyLightDecompose.HLDNode();
                nodes[i].id = i;
            }
            root = nodes[rootId];
        }

        public void updateSubtree(int u, long k) {
            segment.update(nodes[u].dfsOrderFrom, nodes[u].dfsOrderTo, 1, n, k);
        }

        public void addEdge(int a, int b) {
            nodes[a].next.add(nodes[b]);
            nodes[b].next.add(nodes[a]);
        }

        public void setInitVal(int nodeId, int val) {
            nodes[nodeId].pq.add(val);
        }

        public void pop(int nodeId) {
            HeavyLightDecompose.HLDNode node = nodes[nodeId];
            segment.updateRep(node.dfsOrderFrom, node.dfsOrderFrom, 1, n, node);
        }

        public void finish() {
            dfs(root, null);
            dfs2(root, root);
            segIndexToNode = new HeavyLightDecompose.HLDNode[n + 1];
            for (int i = 0; i < n; i++) {
                segIndexToNode[nodes[i].dfsOrderFrom] = nodes[i];
            }
            segment = new HeavyLightDecompose.Segment(1, n, i -> segIndexToNode[i]);
        }

        public void processPath(int uId, int vId, QueryObject qo) {
            HeavyLightDecompose.HLDNode u = nodes[uId];
            HeavyLightDecompose.HLDNode v = nodes[vId];
            while (u != v) {
                if (u.link == v.link) {
                    if (u.size > v.size) {
                        HeavyLightDecompose.HLDNode tmp = u;
                        u = v;
                        v = tmp;
                    }
                    segment.query(v.dfsOrderFrom + 1, u.dfsOrderFrom, 1, n, qo);
                    u = v;
                } else {
                    if (u.link.size > v.link.size) {
                        HeavyLightDecompose.HLDNode tmp = u;
                        u = v;
                        v = tmp;
                    }
                    segment.query(u.link.dfsOrderFrom, u.dfsOrderFrom, 1, n, qo);
                    u = u.link.father;
                }
            }
            segment.query(u.dfsOrderFrom, u.dfsOrderFrom, 1, n, qo);
        }

        private static void dfs(HeavyLightDecompose.HLDNode root, HeavyLightDecompose.HLDNode father) {
            root.size = 1;
            root.father = father;
            for (HeavyLightDecompose.HLDNode node : root.next) {
                if (node == father) {
                    continue;
                }
                dfs(node, root);
                root.size += node.size;
                if (root.heavy == null || root.heavy.size < node.size) {
                    root.heavy = node;
                }
            }
        }

        private void dfs2(HeavyLightDecompose.HLDNode root, HeavyLightDecompose.HLDNode link) {
            root.dfsOrderFrom = order++;
            root.link = link;
            if (root.heavy != null) {
                dfs2(root.heavy, link);
            }
            for (HeavyLightDecompose.HLDNode node : root.next) {
                if (node == root.father || node == root.heavy) {
                    continue;
                }
                dfs2(node, node);
            }
            root.dfsOrderTo = order - 1;
        }

        public static class Segment implements Cloneable {
            private HeavyLightDecompose.Segment left;
            private HeavyLightDecompose.Segment right;
            private long val;
            private long minVal;
            private int minIndex;
            private static long inf = (long) 1e18;

            public void pushUp() {
                minVal = Math.min(left.minVal, right.minVal);
                minIndex = minVal == left.minVal ? left.minIndex : right.minIndex;
            }

            public void modify(long x) {
                this.val += x;
                this.minVal += x;
            }

            public void pushDown() {
                if (val != 0) {
                    left.modify(val);
                    right.modify(val);
                    val = 0;
                }
            }

            public void replace(HeavyLightDecompose.HLDNode node) {
                if (node.pq.isEmpty()) {
                    minVal = inf;
                } else {
                    int top = node.pq.remove();
                    minVal = top + val;
                    minIndex = top - 1;
                }
            }

            public Segment(int l, int r, IntFunction<HeavyLightDecompose.HLDNode> function) {
                if (l < r) {
                    int m = DigitUtils.floorAverage(l, r);
                    left = new HeavyLightDecompose.Segment(l, m, function);
                    right = new HeavyLightDecompose.Segment(m + 1, r, function);
                    pushUp();
                } else {
                    HeavyLightDecompose.HLDNode node = function.apply(l);
                    replace(node);
                }
            }

            private boolean covered(int ll, int rr, int l, int r) {
                return ll <= l && rr >= r;
            }

            private boolean noIntersection(int ll, int rr, int l, int r) {
                return ll > r || rr < l;
            }

            public void updateRep(int ll, int rr, int l, int r, HeavyLightDecompose.HLDNode x) {
                if (noIntersection(ll, rr, l, r)) {
                    return;
                }
                if (covered(ll, rr, l, r)) {
                    replace(x);
                    return;
                }
                pushDown();
                int m = DigitUtils.floorAverage(l, r);
                left.updateRep(ll, rr, l, m, x);
                right.updateRep(ll, rr, m + 1, r, x);
                pushUp();
            }

            public void update(int ll, int rr, int l, int r, long x) {
                if (noIntersection(ll, rr, l, r)) {
                    return;
                }
                if (covered(ll, rr, l, r)) {
                    modify(x);
                    return;
                }
                pushDown();
                int m = DigitUtils.floorAverage(l, r);
                left.update(ll, rr, l, m, x);
                right.update(ll, rr, m + 1, r, x);
                pushUp();
            }

            public void query(int ll, int rr, int l, int r, QueryObject qo) {
                if (noIntersection(ll, rr, l, r)) {
                    return;
                }
                if (covered(ll, rr, l, r)) {
                    qo.update(minVal, minIndex);
                    return;
                }
                pushDown();
                int m = DigitUtils.floorAverage(l, r);
                left.query(ll, rr, l, m, qo);
                right.query(ll, rr, m + 1, r, qo);
            }

            private void toString(StringBuilder builder) {
                if (left == null && right == null) {
                    builder.append("val").append(",");
                    return;
                }
                pushDown();
                left.toString(builder);
                right.toString(builder);
            }

            public String toString() {
                StringBuilder builder = new StringBuilder();
                deepClone().toString(builder);
                if (builder.length() > 0) {
                    builder.setLength(builder.length() - 1);
                }
                return builder.toString();
            }

            private HeavyLightDecompose.Segment deepClone() {
                HeavyLightDecompose.Segment seg = clone();
                if (seg.left != null) {
                    seg.left = seg.left.deepClone();
                }
                if (seg.right != null) {
                    seg.right = seg.right.deepClone();
                }
                return seg;
            }

            protected HeavyLightDecompose.Segment clone() {
                try {
                    return (HeavyLightDecompose.Segment) super.clone();
                } catch (CloneNotSupportedException e) {
                    throw new RuntimeException(e);
                }
            }

        }

        public static class HLDNode {
            List<HeavyLightDecompose.HLDNode> next = new ArrayList<>(2);
            int id;
            int dfsOrderFrom;
            int dfsOrderTo;
            int size;
            HeavyLightDecompose.HLDNode link;
            HeavyLightDecompose.HLDNode heavy;
            HeavyLightDecompose.HLDNode father;
            PriorityQueue<Integer> pq = new PriorityQueue<>();

            public String toString() {
                return "" + id;
            }

        }

    }

    static class QueryObject {
        long val;
        int index;

        public void reset() {
            val = (long) 1e18;
        }

        public void update(long val, int index) {
            if (this.val > val) {
                this.val = val;
                this.index = (int) 1e9;
            }
            if (this.val == val) {
                this.index = Math.min(index, this.index);
            }
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int floorAverage(int x, int y) {
            return (x & y) + ((x ^ y) >> 1);
        }

    }

    static class SequenceUtils {
        public static boolean equal(int[] a, int al, int ar, int[] b, int bl, int br) {
            if ((ar - al) != (br - bl)) {
                return false;
            }
            for (int i = al, j = bl; i <= ar; i++, j++) {
                if (a[i] != b[j]) {
                    return false;
                }
            }
            return true;
        }

    }

    static class IntegerArrayList implements Cloneable {
        private int size;
        private int cap;
        private int[] data;
        private static final int[] EMPTY = new int[0];

        public IntegerArrayList(int cap) {
            this.cap = cap;
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
        }

        public IntegerArrayList(IntegerArrayList list) {
            this.size = list.size;
            this.cap = list.cap;
            this.data = Arrays.copyOf(list.data, size);
        }

        public IntegerArrayList() {
            this(0);
        }

        public void ensureSpace(int req) {
            if (req > cap) {
                while (cap < req) {
                    cap = Math.max(cap + 10, 2 * cap);
                }
                data = Arrays.copyOf(data, cap);
            }
        }

        private void checkRange(int i) {
            if (i < 0 || i >= size) {
                throw new ArrayIndexOutOfBoundsException();
            }
        }

        public int get(int i) {
            checkRange(i);
            return data[i];
        }

        public void add(int x) {
            ensureSpace(size + 1);
            data[size++] = x;
        }

        public void addAll(int[] x, int offset, int len) {
            ensureSpace(size + len);
            System.arraycopy(x, offset, data, size, len);
            size += len;
        }

        public void addAll(IntegerArrayList list) {
            addAll(list.data, 0, list.size);
        }

        public int size() {
            return size;
        }

        public int[] toArray() {
            return Arrays.copyOf(data, size);
        }

        public void clear() {
            size = 0;
        }

        public String toString() {
            return Arrays.toString(toArray());
        }

        public boolean equals(Object obj) {
            if (!(obj instanceof IntegerArrayList)) {
                return false;
            }
            IntegerArrayList other = (IntegerArrayList) obj;
            return SequenceUtils.equal(data, 0, size - 1, other.data, 0, other.size - 1);
        }

        public int hashCode() {
            int h = 1;
            for (int i = 0; i < size; i++) {
                h = h * 31 + Integer.hashCode(data[i]);
            }
            return h;
        }

        public IntegerArrayList clone() {
            IntegerArrayList ans = new IntegerArrayList();
            ans.addAll(this);
            return ans;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}