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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
bool debug = false;
vector<int> init_skills;
struct MOD {
  unsigned long long id;
  unsigned long long type;
  unsigned long long skill_id;
  unsigned long long value;
};
struct EVAL {
  MOD mod;
  unsigned long long top;
  unsigned long long bottom;
};
void print_int(int i) {
  if (debug) {
    cout << i << '\n';
  }
}
char get_type_sym(const unsigned long long type) {
  char sym;
  switch (type) {
    case 1:
      sym = '=';
      break;
    case 2:
      sym = '+';
      break;
    case 3:
      sym = '*';
      break;
  }
  return sym;
}
void print_mod(const MOD &m) {
  if (debug) {
    char sym = get_type_sym(m.type);
    cout << m.id << "]" << init_skills[m.skill_id - 1] << "skill:" << m.skill_id
         << "\t" << sym << m.value << '\n';
  }
}
void print_eval(const EVAL &e) {
  if (debug) {
    cout << "skill:" << e.mod.skill_id << "\tw:" << e.top << '/' << e.bottom
         << "\t"
         << "[";
    cout << e.mod.id << get_type_sym(e.mod.type) << "]\n";
  }
}
template <typename T>
void print_vector(const vector<T> &vec) {
  if (debug) {
    std::cout << "vec:";
    for (const T &t : vec) std::cout << t << ' ';
    std::cout << std::endl;
  }
}
template <>
void print_vector(const vector<vector<unsigned long long>::iterator> &vec) {
  if (debug) {
    std::cout << "it_vec:";
    for (const auto &t : vec) std::cout << *t << ' ';
    std::cout << std::endl;
  }
}
bool mod_sorter(const MOD &lhs, const MOD &rhs) {
  const int lhs_type = (lhs.type == 3) ? 3 : 2;
  const int rhs_type = (rhs.type == 3) ? 3 : 2;
  if (lhs.skill_id == rhs.skill_id) {
    if (lhs_type == rhs_type) {
      return lhs.value > rhs.value;
    }
    return lhs_type < rhs_type;
  }
  return lhs.skill_id < rhs.skill_id;
}
bool eval_sorter(const EVAL &lhs, const EVAL &rhs) {
  const unsigned long long lhs_mul = lhs.top * rhs.bottom;
  const unsigned long long rhs_mul = rhs.top * lhs.bottom;
  if (lhs_mul == rhs_mul) {
    return lhs.mod.id < rhs.mod.id;
  }
  return lhs_mul > rhs_mul;
}
int main(int argc, char **argv) {
  for (int i = 0; i < argc; ++i) {
    if (string(argv[i]) == "-test") {
      freopen("input.txt", "r", stdin);
    }
    if (string(argv[i]) == "-debug") {
      debug = true;
    }
  }
  unsigned long long k, n, m;
  cin >> k >> n >> m;
  int init_skill;
  for (unsigned long long i = 0; i < k; i++) {
    cin >> init_skill;
    init_skills.push_back(init_skill);
  }
  vector<MOD> mod_skills;
  unsigned long long a1, a2, a3;
  for (unsigned long long i = 0; i < n; i++) {
    cin >> a1 >> a2 >> a3;
    if (a1 == 1) {
      const unsigned long long init_value = init_skills[a2 - 1];
      if (a3 <= init_value) continue;
      a3 -= init_value;
    }
    mod_skills.push_back({i + 1, a1, a2, a3});
  }
  sort(mod_skills.begin(), mod_skills.end(), &mod_sorter);
  if (debug) {
    for_each(mod_skills.begin(), mod_skills.end(), print_mod);
    cout << endl;
  }
  vector<EVAL> all_evals;
  unsigned long long last_skill_id = 0;
  unsigned long long prev_value = 0;
  bool was_move = false;
  for (const MOD &mod : mod_skills) {
    const unsigned long long skill_id = mod.skill_id;
    const unsigned long long init_value = init_skills[skill_id - 1];
    unsigned long long top;
    unsigned long long bottom;
    if (last_skill_id != skill_id) {
      last_skill_id = skill_id;
      prev_value = init_value;
      was_move = false;
    }
    switch (mod.type) {
      case 1:
        if (was_move) continue;
        was_move = true;
      case 2:
        top = mod.value;
        bottom = prev_value;
        prev_value += mod.value;
        break;
      case 3: {
        if (mod.value < 2) {
          continue;
        }
        top = mod.value - 1;
        bottom = 1;
        break;
      }
    }
    const EVAL new_eval = {mod, top, bottom};
    all_evals.push_back(new_eval);
  }
  sort(all_evals.begin(), all_evals.end(), &eval_sorter);
  if (debug) {
    for_each(all_evals.begin(), all_evals.end(), print_eval);
    cout << '\n';
  }
  unsigned long long mi = m;
  vector<vector<unsigned long long> > result_ids = {{}, {}, {}};
  vector<vector<EVAL> > vector_eval_result = {{}, {}, {}};
  for (const EVAL &eval : all_evals) {
    if (mi == 0) {
      break;
    }
    mi -= 1;
    result_ids[(eval.mod.type - 1)].push_back(eval.mod.id);
    vector_eval_result[(eval.mod.type - 1)].push_back(eval);
  }
  unsigned long long used_m = m - mi;
  cout << used_m << endl;
  if (used_m > 0) {
    for (const auto &lst : result_ids)
      for (const auto id : lst) {
        cout << id << ' ';
      }
  }
  return 0;
}