Soham won the previous Tour de France, so this time his friend Sarthak dares him to find and mark the roads belonging to the ideal tree of the map of Paris with his trusty Magic Marker. Soham is able to do it. Post the race Sharma wants to walk around Paris. He repeatedly chooses two checkpoints and travels between them through only the ideal tree marked by Soham. He also leaves breadcrumbs on the checkpoints of the paths so that Samarth can find him, since his new iPhone runs out of battery very quick. Samarth visits all checkpoints and keeps an array of the number of breadcrumbs retrieved at each checkpoint, but clumsy him, he lost it during customs. Can you help him get the array again. Input First line of input contains two integers N and K which denote the number of checkpoints on the map of paris and number of paths that Sharma chooses post the race The next 2 lines consist of two arrays A, B of size N - 1, which means that there is a road on the ideal tree between A[i] and B[i] for every 1 i N - 1 The next K lines consist of three integers C and D which means Sharma leaves breadcrumbs on the checkpoints when he travels from C to D through the roads marked by Soham. Output For each checkpoint output number of breadcrumbs retrieved by Samarth. (Note: Sharma drops only one breadcrumb on a checkpoint on a single journey) Constraints 1 N 105 o 1 A[i], B[i] N Vi [1, N 1] 1 k 105 1 C, D N Sample Input 85 1 4 5 6 6 3 3 2 1 8 5 7 54 8 4 16 5 7 34 28 Sample Output 2 1 4 1 4 212 Explanation of Input The ideal tree of Paris