\textit{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!} 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. \InputFile The input contains several test cases. In each test case, the first line contains three integers \textbf{n}, \textbf{m}, \textbf{k} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50,000}, \textbf{1} ≤ \textbf{m} ≤ \textbf{100,000}, \textbf{2} ≤ \textbf{k} ≤ \textbf{33333}). Places are numbered from \textbf{1} to \textbf{n}. The second line contains \textbf{n} integers \textbf{V}\[\textbf{i}\] (\textbf{1} ≤ \textbf{V}\[\textbf{i}\] ≤ \textbf{k}), the initial treasure values of each place. Each of the next m lines contains an operation. For each operation, \textbf{1} ≤ \textbf{x}, \textbf{y} ≤ \textbf{n}, 1 ≤ \textbf{v} ≤ \textbf{k}. The input is terminated by end-of-file (\textbf{EOF}). The size of input file does not exceed \textbf{10} MB. \OutputFile For each type-\textbf{3} operation, output the number of places and the product of their treasure values, modulo \textbf{k}. If there is no path between \textbf{x} and \textbf{y}, or every place along the path has treasure value > \textbf{v}, output a single \textbf{0} (rather than \textbf{0 0} or \textbf{0 1}). \textbf{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 \textbf{d} is the last integer that you output, before processing this operation. If you haven't output anything yet, \textbf{d=0}. After the obfuscation, the sample input would be: 4 8 39 2 3 4 5 1 1 2 3 2 3 5 1 1 3 3 2 3 5 1 25 28 3 27 28 28 3 11 12 13 3 4 5 2 This is the real input that your program will read.