D 神给他的妹子买了好多好多的巧克力，放在他的储藏室中。作为爱吃巧克力的小 R，当然要去 D 神的储藏室中偷吃巧克力了。
D 神的储藏室中共有 nnn 个巧克力储藏点，编号从 000 到 n−1，每个储藏点中有一块巧克力。共有 mmm 条单向道路，每条单向路径连接了两个储藏点。小 R 从编号为 000 的储藏点出发，由于他太爱吃巧克力了，他只要经过一个储藏点就一定会吃掉那块巧克力。另外，他不能经过同一个储藏点两次，否则就会触发警报惊动 D 神。
每块巧克力的甜度不同，小 R 吃的第 iii 块巧克力可以感受到 s⋅ki−1 的甜度，其中 sss 是该巧克力本身的甜度，kkk 是给定的不大于 111 的正实数。小 R 感受到的总甜度是他吃每一块巧克力感受到的甜度之和。请给出一条路线使得小 R 感受到的总甜度尽量大。
输入格式
输入文件为 chocolate1.in ~ chocolate10.in。
第一行包含两个正整数 n,mn, mn,m 和一个正实数 k (0≤k≤1)k\ (0 \leq k \leq 1)k(0≤k≤1)，nnn 表示巧克力储藏点的数量，mmm 表示单向道路的数量，kkk 表示甜度的衰减系数。