Optimal Partition#3664
Let be the set containing all natural numbers from to . The task is to split it into two disjoint sets A_1 and A_2 (A_1 \cap A_2 = \emptyset, A_1 \cup A_2 = A). Let N_1 and N_2 denote the number of elements in A_1 and A_2 respectively, and S_1 and S_2 denote the sum of their elements. Define \Delta N = |N_1 - N_2| and \Delta S = |S_1 - S_2|. Two optimality criteria are given: one for , the other for . Each criterion can require either maximization or minimization of its value.
Your task is to find a partition which is optimal according to the first given criterion. If there are several such partitions, select among them one that is optimal according to the second criterion. If there are still multiple, you may output any of them.
The first line of input contains a positive integer (1 \leq N \leq 10^6). The second and third lines specify the first and second criteria, respectively. The first character of each line is either N (for ) or S (for ), followed by a space and then the requirement for that criterion: min (minimize) or max (maximize).
Print two lines, each describing one of the sets A_1 and A_2. The first number in each line should be the number of elements in the set, followed by all the elements of the set in increasing order.
Example 1