A complex cryptosystem works as follows:

You have n words and if you put a vertex for any word in the graph, then you will use some edges between them and color each one of them

In this system, a key is defined as follows:

(c₁,c₂,...,c_|c|)*k which means that the order(c₁,c₂,...,c_|c|) repeats k times

For example, the key (1,2)*3 =(1,2,1,2,1,2) (1 and 2 are colors) or the key (3,8,1)*2 = (3,8,1,3,8,1).

So, a color can repeat multiple times as shown in the example.

In order to use two words instead of each other, the set of paths between them must be in the following order:

Note: In a path, a vertex and an edge can be repeated multiple times.

1. The edges in the path must be exactly like the key.

2. The number of paths with the given condition must be greater than or equal p (for security).

You are given a graph with colored edges, key, two vertices, and p.

You need to find out if there is a set of paths that follows the order between those two vertexes.

Input format

• First line: Six integers n,m,p,|c|,u,v (1<=n<=100 , 1<=u,v<=n , 1<=m<=n*(n-1)/2, 1<=p<=100 , 1<=|c|<=20)
  • n is number of words
  • m is the number of edges(in-built graph)
  • p is defined in the second order 
  • u and v show the 2 words used instead of each other
• Second line: |c| integer representing the key colors and an integer k representing the number of reputation (1<=c_i<=20 , 1<=k<=1000000),
• Each of the last m lines: 3 integers x,y, and w indicating that there is an edge between x and y with the color w(1<=x, y< =n, 1<=w<=20).

Output format

    Print YES, if there is a set of paths and NO otherwise.