D 神给他的妹子买了好多好多的巧克力，放在他的储藏室中。作为爱吃巧克力的小 R，当然要去 D 神的储藏室中偷吃巧克力了。
D 神的储藏室中共有n个巧克力储藏点，编号从 0 到n-1，每个储藏点中有一块巧克力。共有m条单向道路，每条单向路径连接了两个储藏点。小R从编号为 0 的储藏点出发，由于他太爱吃巧克力了，他只要经过一个储藏点就一定会吃掉那块巧克力。另外，他不能经过同一个储藏点两次，否则就会触发警报惊动 D 神。
每块巧克力的甜度不同，小R吃的第i块巧克力可以感受到sk^i-1的甜度，其中s是该巧克力本身的甜度，k是给定的不大于 1 的正实数。小 R 感受到的总甜度是他吃每一块巧克力感受到的甜度之和。请给出一条路线使得小 R 感受到的总甜度尽量大。

第一行包含两个正整数n,m和一个正实数k(0<k≤1)，n表示巧克力储藏点的数量，m表示单向道路的数量，k表示甜度的衰减系数。
第二行n个正整数，分别表示每块巧克力的甜度。
接下来m行，每行两个正整数u,v，表示有一条从u到v的一条单向边。

第一行一个非负整数L，表示路径长度。
第二行L个正整数，分别表示经过每一个储藏点的标号。