URI Online Judge | 2572

Line-up

By Gabriel Poesia, UFMG BR Brasil

Timelimit: 4

Climbing a team is a tricky task in many sports. For example, in football, if we build a team with the 11 best football players of all time, we would probably have a team with no goalkeeper or defender.

The case is a bit simpler in Pokémon Ho. In this game, each player has their set of critters, called Pokémon, that can battle each other. In a battle between two coaches, each one must choose a set of up to K Pokémon to battle. A team does not have to have K Pokémon, but it must have at least one. Each Pokémon has an attack multiplier, and the total damage dealt by all Pokémon is simply the product of the multipliers of all Pokémon on the trainer's team. This product is called total attack. Since the interaction between Pokémon multipliers is simpler than between players in a team sport, it is not so difficult to choose the Pokémon that maximizes the total attack for a battle.

Before launching the game, NlogNintendo is evaluating the teams that can be formed in each region of the world. There are N Pokémon in the game, numbered 1 to N. For each region of the world, NlogNintendo decided to release only a few Pokémon. Thus, to capture all Pokémon, players would have to travel through several countries, which makes the experience more interesting (although more expensive). To simplify the choice, it was decided that each region will have access to a contiguous part of the Pokémon sequence. More precisely, in region i, players have access to the Pokémon of numbers L_i, L_{i}+1, ..., R_{i} - 1R_{i}, that is, all Pokémon with numbers between L_i And R_i.

Given the attack multipliers of each Pokémon, the sequence of Pokémon available in each region, and the maximum K size of the teams that can battle, the company has hired you to tell you which is the best possible all-around attack anyone could make with just the Pokémon Of each region.

Input

The entry starts with a line containing three integers separated by space: <  2*10) (number of Pokémon in the game), KK < 40 ) (maximum size of a team of Pokémon that can battle) and < 2*105 ) (number of regions in the game). Then the next line contains N integers m_i ( 0 < m_i 104 ) separated by space, where m_i is the Pokémon's attack multiplier of number i. Finally, there are R lines describing which Pokémon are available in each region. Each of these lines contains two integers, L_i and R_i (1 L_i < R_i < N), meaning that in the i-th region of the game only Pokémon with numbers between L_i and R_i are available.

Output

The output contains R rows. On the i-th line, print an integer: the total attack of the best team of up to K Pokémon that can be formed with the Pokémon available in the i-th region. Since this number can be very large, print your remainder of the division by 109 + 7.

Input Sample Output Sample

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

3
8
12