Antidote

In the 23rd century a virus with the codename ECN-2202 (Easy to Cure and Neutralize 2202) is making victims within the population. Mankind is heading towards social and economical disaster. A large research group is trying to find an antidote; they are using programming contests to find and run simulations of possibly good vaccines. The vaccine has two components: VacA and VacB. The research process results in n different VacA components and m different VacB components, described through their aggressiveness of the effect on the human organism. The components work in pairs, and every VacA is compatible with any of the VacB components, their aggressiveness is the cumulated aggressiveness of the two parts. The more aggressive the vaccine, the more effective it is. But too much aggressiveness can really hurt the body of the patient.

After many discussions, the scientists came up with a testing plan. They decide to leave the least effective vaccines apart, and to do so with the most aggressive ones too. To set the range, they set a lower and an upper bound for the effectiveness, but given that there can be up to 200 000 different components which can be combined, they can only set theoretical bounds. According to this, only those vaccines are eligible for testing which are strictly more effective than the Ath element and strictly less aggressive than the Bth element in the list of (VacA, VacB) in increasing ordered list of the cumulative aggressiveness. Given the increasingly ordered list of VacA and VacB components, help them figure out which combinations are in the tolerable range of aggressiveness, not to make many casualties in the trial.

Input Specification

The first line contains four space-separated integers: n is the cardinality of VacA components, m is the cardinality of VacB components, A is the index of the lower bound of the eligible combinations, B is the upper bound of the eligible combinations. The two indexes are considered in the increasing ordered list of all (VacA_i, VacB_j) combinations’ cumulated aggressiveness (1 ≤ i ≤ n, 1 ≤ j ≤ m).

The next n lines contain the VacA components’ aggressiveness values as integers in increasing order.

The next m lines contain the VacB components’ aggressiveness values as integers in increasing order.

Output Specification

The first line of the output should contain K, the total number of eligible vaccines.

The next K lines are formed by the index pairs of eligible (VacA_i, VacB_j) combinations, where

the Ath element in the ordered list of combinations < (VacA_i, VacB_j), and

(VacA_i, VacB_j) < the Bth element in the ordered list of combinations.

The eligible vaccines are sorted by the first component, then, in case of equality, by the second component.

Input Limits and Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ m ≤ 10⁵
• 1 ≤ VacA_i ≤ 10⁹ (1 ≤ i ≤ n)
• 1 ≤ VacB_i ≤ 10⁹ (1 ≤ i ≤ m)
• 1 ≤ A < B ≤ n · m
• 0 ≤ B – A ≤ 10⁵

Sample Input

1. 3 5 2 5
2. 1 
3. 5 
4. 6
5. 3
6. 3
7. 3
8. 4
9. 6

download as text file

Output for Sample Input

1. 1
2. (1,4)

download as text file

Explanation

The 2nd element in the ordered list of combinations is (1, 2), with a value of 1 + 3 = 4.

The 5th element in the ordered list of combinations is (1, 5), with an effectiveness of 1 + 6 = 7.

The only value between the two boundaries, which is strictly greater than 4 and strictly less than 8, is (1, 4) with an effectiveness value of 5.