Cat Davy has a weighted directed graph with n nodes and m edges.

Each node has a color between 1 and c.

Consider a partition of the nodes into disjoint sets S and T (with T equal to the complement of S). The raw cost of the cut is the difference between the sum of edge weights going from set S to T and the sum of edge weights going from T to S. Davy likes partitions with large raw costs.

Davy would like to partition the cut so that nodes with the same color are in the same side of the partition. However, he realizes that it actually might decrease the raw cost of the cut by too much, so he is willing to compromise. More specifically, given a partition \(S,T\), let \(k_i\) = \(\min\)(number of nodes with color i in S, number of nodes with color i in T). Let K be the sum of \(k_i\) over all colors. Then, the net cost of the cut is equal to the raw cost minus \(K^2\).

Davy is having trouble finding the best partition, so he asks for your help. You do not have to find an optimal solution, so your score will depend on the net cost of the set that you output. A higher net cost will lead to a higher score.

Scoring details:

If your solution is less than zero, it will receive zero. Otherwise, your score for the test case is equal to the net cost divided by the sum of all edge weights in S.

Input format:

The first line of input will contain three integers \(n,m,c\).
The next line of input will contain n integers. The i-th integer denotes the color of the i-th node.
The following m lines will contain three integers \(u_i, v_i, w_i\). This denotes a directed edge from node \(u_i\) to \(v_i\) with weight \(w_i\).

Output format:

In the first line of output, print a single integer denoting the size of your set.
In the second line, output the indices of the nodes in the set.

Constraints

These can be inferred from the test case generation section.

Test case generation:

You may use the following python code to construct the test cases (the sample is an exception)

import random
def f(lo,hi):
    # returns a random integer from lo to hi inclusive
    e = random.randint(0,3)
    n = random.randint(lo, hi)
    for x in range(e):
        n = random.randint(lo, n)
    return n

n = f(100, 100000)
m = f(n, min(100000, n * (n - 1) / 2))
c = f(1, n)

choices = []
for i in range(c):
    choices.extend([i+1]*f(1,20))
colors = [random.sample(choices, 1)[0] for i in range(n)]

print n,m,c
print " ".join(map(str, colors))
for i in xrange(m):
    u,v = random.sample(xrange(n), 2)
    u += 1
    v += 1
    w = f(1, 10000)
    print u,v,w

The test cases during the contest are 20 randomly generated cases from the above code. After the contest, 180 additional cases will be generated and your score on all 200 cases will correspond to your final score.