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 *a*<sub class="lower-index">*i*</sub>. 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*; 1.  add *b* to the *i*-th skill; 1.  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.
The first line contains three numbers — *k*, *n*, *m* (1 ≤ *k* ≤ 10<sup class="upper-index">5</sup>, 0 ≤ *m* ≤ *n* ≤ 10<sup class="upper-index">5</sup>) — 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*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>), the initial values of skills.

Next *n* lines contain 3 space-separated numbers *t*<sub class="lower-index">*j*</sub>, *i*<sub class="lower-index">*j*</sub>, *b*<sub class="lower-index">*j*</sub> (1 ≤ *t*<sub class="lower-index">*j*</sub> ≤ 3, 1 ≤ *i*<sub class="lower-index">*j*</sub> ≤ *k*, 1 ≤ *b*<sub class="lower-index">*j*</sub> ≤ 10<sup class="upper-index">6</sup>) — 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.
'''
Solución del problema [521D] Shop.
https://codeforces.com/problemset/problem/521/D
'''

from bisect import bisect_left as lower_bound

ASSIGN_T, ADD_T, MULT_T = 0,1,2


def solve_shop(a: list, b: list, m: int):
    '''
    Modifica los valores de las transformaciones de tipos no multiplicativos a 
    expresiones multiplicativas, conservando las referencias a tipos originales
    y cual valor `a_i` modifican.

    `a`: los valores de la lista a optimizar.
    `b`: las transformaciones de entrada.
    '''
    k,n = len(a), len(b)

    # Ordenamos `b` aprovechando la ordenación por defecto de las tuplas (j,t,v) para
    # recorrer transformaciones en orden del a[j] asociado, que a su vez están ordenadas
    # por tipo (asignación, luego adición, luego multiplicación). Las transformaciones
    # de igual tipo estarán entonces ordenadas por valores (notar que estos últimos
    # quedarán de forma ascendente).
    b.sort()

    # Agrupamos por tipo y por correspondencia a cada elemento de `a`.
    # De forma que para la i-ésima transformación que modifica a `a[j]`` se almacena el valor y el índice j.
    by_type = tuple([[] for _ in range(k)]  # una lista por cada a[i].
                        for _ in range(3))  # k listas por cada tipo.
    for i,(j,t,v) in enumerate(b):
        by_type[t][j].append((v,i))

    # Se tratan las transformaciones (+,=) por cada a[j], se llevan a forma (*).
    # Se juntan todas las transformaciones en b_mult.
    b_mult = []
    for j in range(k):
        # Tomamos la máxima asignación de a[j] y decidimos si utilizarla.
        max_v, i = max(by_type[ASSIGN_T][j], default=(0,0))
        if max_v > a[j]:
            x = (max_v - a[j], i)
            index = lower_bound(by_type[ADD_T][j], x)
            by_type[ADD_T][j].insert(index, x)

        # Tomamos las adiciones y las llevamos a multiplicaciones. Por la
        # ordenación inicial de `b`, los valores están ya ordenados aunque de forma
        # ascendente, por los que se toman en orden inversos ([::-1]).
        acc = a[j]
        for v,i in by_type[ADD_T][j][::-1]:
            b_mult.append(((acc+v)/acc,i))
            acc += v
        
        # Añadimos las transformaciones de multiplicación.
        b_mult.extend(by_type[MULT_T][j])
    
    # Ordenamos por mayor valor de la transformación.
    b_mult.sort(reverse=True)
    selected = set(i for _,i in b_mult[:m])

    # Devolvemos la lista de transformaciones aplicadas en el orden establecido.
    # TODO! esto no funciona porque los b con mismo a_i y tipo, estan ascendientes.
    answer = []
    for i in range(n):
        if i in selected:
            answer.append(i)
    
    return answer


if __name__ == '__main__':

    # De los datos de entrada, se obtienen A, lista de tamaño k de los valores a
    # optimizar y B la lista de transformaciones disponibles, tamaño n.
    k,n,m = map(int, input().split())
    A = [int(a) for a in input().split()]
    B = []
    for _ in range(n):
        t,j,v = map(int, input().split())

        # Invertimos las tuplas a j,t,v para garantizar el orden deseado.
        B.append((j-1,t-1,v))
    
    answer = solve_shop(A, B, m)
    
    # Imprimimos la respuesta.
    print(len(answer))
    for i in answer:
        print(i+1)
    