Problem: Vasya plays one very well-known and extremely popular MMORPG game. His game character has k skill; currently the i-th of them equals to ai. Also this game has a common rating table in which the participants are ranked according to the product of all the skills of a hero in the descending order.

Vasya decided to 'upgrade' his character via the game store. This store offers n possible ways to improve the hero's skills; Each of these ways belongs to one of three types:

  1. assign the i-th skill to b; 
  2. add b to the i-th skill; 
  3. multiply the i-th skill by b. 



Unfortunately, a) every improvement can only be used once; b) the money on Vasya's card is enough only to purchase not more than m of the n improvements. Help Vasya to reach the highest ranking in the game. To do this tell Vasya which of improvements he has to purchase and in what order he should use them to make his rating become as high as possible. If there are several ways to achieve it, print any of them.

Input

The first line contains three numbers — k, n, m (1 ≤ k ≤ 105, 0 ≤ m ≤ n ≤ 105) — the number of skills, the number of improvements on sale and the number of them Vasya can afford.

The second line contains k space-separated numbers ai (1 ≤ ai ≤ 106), the initial values of skills.

Next n lines contain 3 space-separated numbers tj, ij, bj (1 ≤ tj ≤ 3, 1 ≤ ij ≤ k, 1 ≤ bj ≤ 106) — the type of the j-th improvement (1 for assigning, 2 for adding, 3 for multiplying), the skill to which it can be applied and the value of b for this improvement.

Output

The first line should contain a number l (0 ≤ l ≤ m) — the number of improvements you should use.

The second line should contain l distinct space-separated numbers vi (1 ≤ vi ≤ n) — the indices of improvements in the order in which they should be applied. The improvements are numbered starting from 1, in the order in which they appear in the input. 

Examples

Input

2 4 3
13 20
1 1 14
1 2 30
2 1 6
3 2 2


Output

3
2 3 4

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.AbstractQueue;
import java.io.IOException;
import java.util.ArrayList;
import java.io.UncheckedIOException;
import java.util.List;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Comparator;
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);
            DShop solver = new DShop();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DShop {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int k = in.ri();
            int n = in.ri();
            int m = in.ri();
            Skill[] skills = new Skill[k];
            for (int i = 0; i < k; i++) {
                skills[i] = new Skill();
                skills[i].init = in.ri();
            }
            for (int i = 0; i < n; i++) {
                Op op = new Op();
                op.id = i;
                op.t = in.ri();
                Skill item = skills[in.ri() - 1];
                op.v = in.ri();
                if (op.t == 1) {
                    if (op.v > item.init) {
                        if (item.assign == null || item.assign.v < op.v) {
                            item.assign = op;
                        }
                    }
                } else if (op.t == 2) {
                    item.plus.add(op);
                } else {
                    item.mul.add(op);
                }
            }

            PriorityQueue<Skill> pq = new PriorityQueue<>(k, Comparator.<Skill, State>comparing(x -> x.now, State.comp).reversed());
            for (Skill skill : skills) {
                if (skill.assign != null) {
                    skill.assign.v = skill.assign.v - skill.init;
                    skill.plus.add(skill.assign);
                }
                skill.plus.sort(Comparator.comparingInt(x -> -x.v));
                skill.mul.sort(Comparator.comparingInt(x -> -x.v));
                skill.lastPick = skill.now = new State(-1, -1, 1, 1, skill.init);
                skill.computeNext();
                if (skill.now != null) {
                    pq.add(skill);
                }
            }

            int cnt = 0;
            for (int i = 0; i < m && pq.size() > 0; i++) {
                Skill head = pq.remove();
                head.lastPick = head.now;
                head.computeNext();
                if (head.now != null) {
                    pq.add(head);
                }
                cnt++;
            }
            out.println(cnt);
            for (Skill skill : skills) {
                State last = skill.lastPick;
                boolean useAssign = false;
                for (int i = 0; i <= last.plus; i++) {
                    Op x = skill.plus.get(i);
                    if (x.t == 1) {
                        useAssign = true;
                    }
                }
                if (useAssign) {
                    out.append(skill.assign.id + 1).append(' ');
                }
                for (int i = 0; i <= last.plus; i++) {
                    Op x = skill.plus.get(i);
                    if (x.t == 2) {
                        out.append(x.id + 1).append(' ');
                    }
                }
                for (int i = 0; i <= last.mul; i++) {
                    Op x = skill.mul.get(i);
                    out.append(x.id + 1).append(' ');
                }
            }
        }

    }

    static class LongProduct implements Comparable<LongProduct> {
        long[] data = new long[4];
        int sign;

        public void mul(long a, long b) {
            if (a == 0 || b == 0) {
                sign = 0;
                data[0] = data[1] = data[2] = data[3] = 0;
                return;
            }
            sign = 1;
            if (a < 0) {
                a = -a;
                sign = -sign;
            }
            if (b < 0) {
                b = -b;
                sign = -sign;
            }
            long ha = a >>> 32;
            long la = a & DigitUtils.INT_TO_LONG_MASK;
            long hb = b >>> 32;
            long lb = b & DigitUtils.INT_TO_LONG_MASK;
            long lalb = la * lb;
            long lahb = la * hb;
            long halb = ha * lb;
            long hahb = ha * hb;
            data[0] = lalb & DigitUtils.INT_TO_LONG_MASK;
            data[1] = (lalb >>> 32) + (lahb & DigitUtils.INT_TO_LONG_MASK) +
                    (halb & DigitUtils.INT_TO_LONG_MASK);
            data[2] = (lahb >>> 32) + (halb >>> 32) + (hahb & DigitUtils.INT_TO_LONG_MASK);
            data[3] = (hahb >>> 32);
            data[2] += data[1] >>> 32;
            data[1] &= DigitUtils.INT_TO_LONG_MASK;
            data[3] += data[2] >>> 32;
            data[2] &= DigitUtils.INT_TO_LONG_MASK;
        }

        public int compareTo(LongProduct o) {
            if (sign != o.sign) {
                return Integer.compare(sign, o.sign);
            }
            for (int i = 3; i >= 0; i--) {
                if (data[i] != o.data[i]) {
                    return Long.compare(data[i], o.data[i]) * sign;
                }
            }
            return 0;
        }

        public String toString() {
            return (sign == -1 ? "-" : "") + Arrays.toString(data);
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        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;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

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

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

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

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

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

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

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

        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();
        }

    }

    static class DigitUtils {
        public static long INT_TO_LONG_MASK = (1L << 32) - 1;

        private DigitUtils() {
        }

    }

    static class Skill {
        int init;
        Op assign;
        List<Op> plus = new ArrayList<>();
        List<Op> mul = new ArrayList<>();
        State now;
        State lastPick;

        void computeNext() {
            State best = null;
            if (now.plus + 1 < plus.size()) {
                best = new State(now.plus + 1, now.mul, (plus.get(now.plus + 1).v + now.sum), now.sum, plus.get(now.plus + 1).v + now.sum);
            }
            if (now.mul + 1 < mul.size()) {
                State cand = new State(now.plus, now.mul + 1, mul.get(now.mul + 1).v, 1, now.sum);
                if (best == null || State.comp.compare(best, cand) < 0) {
                    best = cand;
                }
            }
            now = best;
        }

    }

    static class Op {
        int id;
        int t;
        int v;

    }

    static class State {
        int plus;
        int mul;
        long a;
        long b;
        long sum;
        static Comparator<State> comp = (a, b) -> {
            return FractionComparator.compare(a.a, a.b, b.a, b.b);
        };

        public State(int plus, int mul, long a, long b, long sum) {
            assert a >= 0 && b >= 0;
            this.plus = plus;
            this.mul = mul;
            this.a = a;
            this.b = b;
            this.sum = sum;
//        approx = (double) a / b;
        }

    }

    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 ri() {
            return readInt();
        }

        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 FractionComparator {
        static LongProduct p1 = new LongProduct();
        static LongProduct p2 = new LongProduct();

        public static int compare(long a, long b, long c, long d) {
            if (b < 0) {
                a = -a;
                b = -b;
            }
            if (d < 0) {
                c = -c;
                d = -d;
            }
            p1.mul(a, d);
            p2.mul(b, c);
            return p1.compareTo(p2);
        }

    }
}