Ming is on a map. There are �n vertexes in the map. For each vertex, there is only one one-way edge that can reach another vertex on the map.
Ming has a number �y in his hand, and when he reaches a certain vertex �i, the number in his hand will change to �×��+��y×ki+bi.
There are several inquiries, each query Ming will start from a vertex �x and walk �l steps. At each step Ming starts from the current vertex and proceeds along the outgoing arc of that vertex to the next vertex. The initial number in his hand is �y, and he wants to know what the number in his hand will become in the end.The answer is modulo 109+7109+7
The first line, input a positive integer �(1≤�≤5)T(1≤T≤5), representing the number of test data.
For each test, first line input a row of two positive integers �,�(1<�,�≤105)n,q(1<n,q≤105), representing the number of points in the map and the number of queries.
The next line inputs �n positive integers ��(1≤��≤105)ki(1≤ki≤105) representing the value of �k on each vertex
The next line inputs �n positive integers ��(1≤��≤105)bi(1≤bi≤105) representing the value of �b on each vertex
The next line inputs �n positive integers ��(1≤��≤�)pi(1≤pi≤n) represents the vertex reachable from vertex �i, guaranteeing ��≠�pi=i.
The next �q lines,each line has three positive integers ��,��,��(1≤��≤�,1≤��≤109,1≤��≤105)xi,li,yi(1≤xi≤n,1≤li≤109,1≤yi≤105) for a query,��xi is the vertex where Ming started, ��li is the number of steps Ming took, and ��yi is the number in Ming's hand.
1
5 5
2 3 1 2 4
3 4 2 1 2
2 3 5 1 4
1 2 4
2 4 5
3 3 4
4 5 2
5 2 118
125
77
221
9