Scouts on Ranging

All submissions for this problem are available.
During the summer, the boyscouts group decides to go out for a ranging. The teacherincharge Mr. Anderson is faced with the tough job of forming groups for this ranging. Every student in the boyscouts group has a rank. Now Mr. Anderson has to ensure that every group has a group leader whose rank is greater than or equal to the other group members rank, and his age should not differ from the other members in the group by more than K years.
Now many students are friends and they want their group to be as large as possible.
So they approach Mr. Anderson in pairs to ask the largest group size in which that pair can be accommodated.
Since the scouts are large in number, Mr. Anderson is finding it difficult to answer the students and hence comes to you to solve his problem.
Input
First line contains two integers N (1 ≤ N ≤ 100000) and K(1 ≤ K ≤ 10^{7}), number of scouts and the age difference limit in a group. Each scout has a unique serial number from 1 to N.
Next line contains N space separated integers r_{1},r_{2},...,r_{N} (1 ≤ r_{i} ≤ 10^{9}), representing the ranks of scouts in order of their serial number. Ranks may be same for two scout.
Then next line again contains N integers a_{1},a_{2},...,a_{N} (1 ≤ a_{i} ≤ 10^{9}), representing the age of scouts in order of their serial number.
Next line contain number of queries, q (1 ≤ q ≤ 10^{5}). Then q lines follow.
i^{th} line contains two integers each X_{i} and Y_{i} separated by a space, the serial number of the scouts who need be accommodated to largest group.
Output
Output q lines, each containing an integer, maximum group size in which the two scouts queried X_{i} and Y_{i} can be accommodated. The scouts may or may not be the leader of the group.
Example
Input: 6 1 2 5 3 4 3 4 2 4 3 2 1 3 3 2 6 3 6 2 4 Output: 3 5 1 Explanation: For the first query, Serial number are 2 and 6, the largest group size is 3 (serial 2,3,6), group leader is 2.
For the second query, Serial number are 3 and 6, the largest group size is 5 (serial 1,3,4,5,6),
group leader is 4.
In third query, scout 2 has maximum rank, so he is leader, but his age difference with scout 4 is 2,
violating the age restriction. Hence no group can be formed.
Author:  amitpandeykgp 
Tags  amitpandeykgp 
Date Added:  28012013 
Time Limit:  0.247525 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 