Minimax matching#640
Given a complete bipartite graph with two parts, each containing vertices. Each vertex has an integer weight. The weight of an edge is defined as the product of the weights of the two vertices it connects.
A matching in the graph is a set of edges, none of which share a vertex. A matching is called perfect if it covers all vertices of the graph, that is, each vertex is incident to some edge of the matching.
You are required to find a perfect minimax matching; that is, a perfect matching such that the maximum weight among the chosen edges is as small as possible.
The first line contains an integer (1 \leq N \leq 10^5). The second line contains integers, each with absolute value not exceeding 10^9, representing the weights of the vertices in the first part. The third line contains integers in the same manner, representing the weights of the vertices in the second part. The vertices in each part are numbered from to .
Print a single integer — the weight of the perfect minimax matching, i.e., the maximum weight among its edges. In the second line, output the description of such a matching: integers, where the -th integer is the number of the vertex in the second part that is matched by an edge to the -th vertex in the first part.
Example 1