Median of Unions
Given N non-decreasing sequences of integers, where each sequence contains exactly L elements. For every pair of sequences, perform the following operation: merge their elements into a single sequence (each number appears as many times as it does in the original sequences), sort this merged sequence in non-decreasing order, and find the element at position L in this sequence of 2L elements. This element is referred to as the left median.
Write a program that outputs the left median for each pair of sequences.
Input
First, input the numbers N and L (2 ≤ N ≤ 200, 1 ≤ L ≤ 50000). The next N lines provide the parameters defining each sequence.
Each sequence is specified by five integer parameters: x_1, d_1, a, c, m. The sequence elements are calculated as follows: x_1 is given, and for all i from 2 to L, x_{i} = x_{i-1} + d_{i-1}. The sequence d_i is defined as: d_1 is given, and for i ≥ 2, d_i = ((a·d_{i-1} + c) mod m), where mod denotes the remainder operation of dividing (a·d_{i-1} + c) by m.
The following constraints apply to all sequences: 1 ≤ m ≤ 40000, 0 ≤ a < m, 0 ≤ c < m, 0 ≤ d_1 < m. It is guaranteed that all elements of all sequences do not exceed 10^9 in absolute value.
Output
Output the left median of the union of the 1-st and 2-nd sequences on the first line, the union of the 1-st and 3-rd on the second line, and so on, until the (N-1)-th line, which should contain the median of the union of the 1-st and N-th sequences. Then, output the median of the union of the 2-nd and 3-rd, 2-nd and 4-th, continuing up to the 2-nd and N-th, followed by the 3-rd and 4-th, and so on. The last line should contain the median of the union of the (N-1)-th and N-th sequences.