The Kingdom of Hobbits
Limits: 2 sec., 256 MiB
All the Hobbits like their King Hobbot The Fourth. On his birthday they decided to make a great celebration. It should last for at least \(A\) and at most \(B\) days. The celebration has to begin this day or later, but also it has to end no later than day \(C\) (assume that this day is the day one).
After the celebration the King will cheer up all the Hobbits with gold coins. The King is very heat-loving, thus the number of gold coins depends on how warm the celebration would be. To be precise, the King will award his people with the number of gold coins equal to the minimal temperature during the celebration multiplied by the number of celebration days.
You are given the information about the temperature during \(C\) days (starting from this day) and you have to find the minimal and maximal possible number of gold coins the Hobbits will receive.
Input
The first line contains three integer numbers \(A\), \(B\) and \(C\) separated by single spaces. The second line contains \(C\) integer numbers \(t_i\) separated by single spaces. Here, \(t_i\) is the temperature during the day \(i\).
Output
Print two lines. The first line should contain three integer numbers separated by single spaces — the minimal possible number of coins the Hobbits will receive, the starting and the ending days of the celebration that will result in this number of coins. In case of a tie choose the longer celebration and if there is still a tie choose the one that starts earlier. The second line should contain the same information for the maximal number of gold coins.
Constraints
\(1 \le A \le B \le C \le 10^5\),
\(1 \le t_i \le 10^5\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 2 4 7 1 2 3 4 3 2 1 | 2 1 2 9 3 5 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|