1698: 사과 수확하기

세종과수원에 n개의 사과나무가 한 줄로 심어져 있다.
각 나무에서 수확할 수 있는 사과의 개수가 순서대로 주어진다.


d개의 연속적인 나무에서 사과를 수확할 때, 가장 많이 수확할 수 있는 구간의 총 수확가능한 사과 수를 구하려고 한다.
그런데 과수원을 지키는 요정이 몇번의 마법을 부려 일부 사과나무의 위치를 바꾸어 버렸다.
입력 예시의 경우 마법을 부리기 전과 후로 d개의 사과 나무에서 수확할 수 있는 사과의 최대 개수는 아래와 같다.





요정이 마법을 부리기 전에 연속된 d개의 사과나무에서 수확할 수 있는 사과의 최대 개수와
요정이 마법을 부린 후 연속된 d개의 사과나무에서 수확할 수 있는 사과의 최대 개수를 구하는 프로그램을 작성하시오.

첫번째 줄에 사과나무의 개수가 입력된다.
두번째 줄에 n개의 사과 나무에서 수확할 수 있는 사과의 개수 a_i가 공백으로 구분되어 입력된다.
세번째 줄에 한번에 수확할 수 있는 연속적인 사과나무의 개수 d가 입력된다.
네번째 줄에 요정이 마법을 부리는 횟수 k가 입력된다.
다섯번째 줄에 마법이 적용되어 위치가 바귀는 두 사과나무의 번호 c_i와 c_j가 공백으로 구분하여 입력된다.


[입력값의 범위]
1 ≤ n ≤ 100,000
1 ≤ a_i ≤1,000
1 ≤ d ≤ n
1 ≤ k ≤ 10
1 ≤ c_i, c_j ≤ n

요정이 마법을 부리기 전과 후에 d개의 연속적인 나무에서 가장 많이 수확할 수 있는 구간의 총 사과 수를 공백으로 구분하여 출력한다.

3
8 10 2
2
2
1 2
2 3

18 12

[입력예시2]
6
3 6 7 6 2 3
4
3
4 1
4 2
1 3


[출력예시2]
22 22