Second Generation Turing Machine Test

The second generation Turing machine simulates the process by which deer (metaphorically) perform arithmetic using pen and paper. It is assumed that the machine can perform two elementary operations:

• Write a digit on one cell of a tape.
• Color a segment of the tape.

To test the performance of the machine, Abbi proposed the following two tests (the Turing test):

1. Find, in the interval \([l,r]\), a subinterval that contains all \(c\) colors and has the minimum digit sum among all such subintervals. Output its digit sum. If there is no subinterval containing all \(c\) colors, output \(-1\).
2. Find, in the interval \([l,r]\), a subinterval whose colors are all distinct (i.e. no repeated colors) and has the maximum digit sum among all such subintervals. If no valid subinterval exists, output \(-1\).

You are given the tape information and several queries. Help the machine pass all of Abbi's Turing tests!

inputFormat

The input consists of multiple lines:

1. The first line contains three integers \(n\), \(c\) and \(q\) representing the length of the tape, the total number of colors, and the number of queries respectively.
2. The second line contains \(n\) positive integers representing the digits written on the tape.
3. The third line contains \(n\) integers, each in the range \([1, c]\), representing the color painted on each cell.
4. Then \(q\) lines follow, each containing two integers \(l\) and \(r\) (1-indexed) indicating the interval of the tape for the query.

outputFormat

For each query, output two space-separated integers on a new line:

• The first integer is the minimum digit sum among subintervals of \([l,r]\) that contain all \(c\) colors. If no such subinterval exists, output \(-1\).
• The second integer is the maximum digit sum among subintervals of \([l,r]\) with all distinct colors. If no valid subinterval exists, output \(-1\).

sample

5 2 2
1 2 3 4 5
1 2 1 2 1
1 5
2 4

3 9
5 7