Median of Unions#4042
Given non-decreasing sequences of integers, where each sequence contains exactly 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 in this sequence of elements. This element is referred to as the left median.
Write a program that outputs the left median for each pair of sequences.
First, input the numbers and (2 \leq N \leq 200, 1 \leq L \leq 50000). The next lines provide the parameters defining each sequence.
Each sequence is specified by five integer parameters: x_1, d_1, , , . The sequence elements are calculated as follows: x_1 is given, and for all from to , x_{i} = x_{i-1} + d_{i-1}. The sequence d_i is defined as: d_1 is given, and for i \geq 2, d_i = ((a \cdot d_{i-1} + c) \bmod m), where denotes the remainder operation of dividing a \cdot d_{i-1} + c by .
The following constraints apply to all sequences: 1 \leq m \leq 40000, 0 \leq a < m, 0 \leq c < m, 0 \leq d_1 < m. It is guaranteed that all elements of all sequences do not exceed 10^9 in absolute value.
Output the left median of the union of the -st and -nd sequences on the first line, the union of the -st and -rd on the second line, and so on, until the (N-1)-th line, which should contain the median of the union of the -st and -th sequences. Then, output the median of the union of the -nd and -rd, -nd and -th, continuing up to the -nd and -th, followed by the -rd and -th, and so on. The last line should contain the median of the union of the (N-1)-th and -th sequences.
Example 1