Suppose there are n places in the very beginning of Wario Land. The land was almost deprecated, so it does not have any roads at all! You’ll be given m operations. Execute them one by one, and output the results. I love a game series called “Wario Land”, so I’d like to make a very difficult (indeed!!!) problem about it :) A big thank you goes to Erjin Zhou, for the idea and reference code. And a small thank you goes to Wenbin Tang, for reminding me that “Rujia Liu” also contains the letter L! 1xy Wario wants to build a direct road between place x and y. If x and y are already connected (directly or indirectly), ignore this command (because Wario thinks it’s a waste of time!). 2xy Change place x’s treasure value to v. This is due to newly discovered treasures, or treasures that are stolen by someone else. 3xyv Among the places along the path between x and y (including x and y), how many of them have treasure value ≤ v? Wario also needs the product of these treasure values, modulo k (see below). Input The input contains several test cases. In each test case, the first line contains three integers n, m, k (1≤n≤50,000,1≤m≤100,000,2≤k≤33333). Placesarenumberedfrom1ton. Thesecond line contains n integers V [i] (1 ≤ V [i] ≤ k), the initial treasure values of each place. Each of the next m lines contains an operation. For each operation, 1 ≤ x, y ≤ n, 1 ≤ v ≤ k. The input is terminated by end-of-file (EOF). Output For each type-3 operation, output the number of places and the product of their treasure values, modulo k. If there is no path between x and y, or every place along the path has treasure value > v, output a single ‘0’ (rather than ‘0 0’ or ‘0 1’). Obfuscation In order to prevent you from preprocessing the operations, we adopt the following obfuscation scheme: Each type-1 operation becomes 1 x + d y + d Each type-2 operation becomes 2 x + d v + d Each type-3 operation becomes 3 x+d y+d v+d Where d is the last integer that you output, before processing this operation. If you haven’t output anything yet, d = 0. After the obfuscation, the sample input would be: 4 8 39 2345
2/2 112 3235 113 3235 1 25 28 3 27 28 28 3 11 12 13 3452 This is the real input that your program will read. Sample Input 4 8 39 2345 112 3235 113 3235 114 3344 3345 3341 Sample Output 0 3 24 28 31 0