Codeforces Round 295 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Shop

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya plays one very well-known and extremely popular MMORPG game. His game character has *k* skill; currently the *i*-th of them equals to *a*_{i}. 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:

- assign the
*i*-th skill to*b*; - add
*b*to the*i*-th skill; - 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* ≤ 10^{5}, 0 ≤ *m* ≤ *n* ≤ 10^{5}) — 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 *a*_{i} (1 ≤ *a*_{i} ≤ 10^{6}), the initial values of skills.

Next *n* lines contain 3 space-separated numbers *t*_{j}, *i*_{j}, *b*_{j} (1 ≤ *t*_{j} ≤ 3, 1 ≤ *i*_{j} ≤ *k*, 1 ≤ *b*_{j} ≤ 10^{6}) — 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 *v*_{i} (1 ≤ *v*_{i} ≤ *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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2023 00:18:42 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|