Grandpa's Lottery Games

Interview

Time limit1sMemory limit1024 MB

Summary
Given daily lottery spending and winnings, report the overall profit sign, the single day with the largest loss, and the consecutive run with the largest total loss.
Level

Medium4 of 10

Topics
Array, Prefix sum, Implementation, Brute force
Solved
No attempts yet

Problem

Juku's grandpa is an enthusiastic and, in his own opinion, successful lottery player. Juku has doubts about that last claim, so for a while now he has been recording how much grandpa spends on lottery tickets and how much he wins.

Write a program that produces three kinds of statistics about grandpa's lottery games:

  • determine whether his total winnings are greater than or less than what he spent on tickets;
  • find on which day he lost the most money in a single day;
  • find during which run of consecutive days he lost the most money in total.

Input

The first line contains the number of Juku's diary entries NN (1≤N≤1001 \le N \le 100). Each of the next NN lines contains two space-separated integers: on day ii (1≤i≤N1 \le i \le N), the amount spent on tickets PiP_i (0≤Pi≤1000 \le P_i \le 100) and the amount won ViV_i (0≤Vi≤1 000 0000 \le V_i \le 1\,000\,000).

Output

Print exactly three lines, one answer per line.

On the first line print PLUSSIS, MIINUSES, or NULLIS depending on whether grandpa's total winnings are greater than, less than, or equal to his total ticket costs.

On the second line print two space-separated integers PP and SS, where PP is the number of the day on which grandpa lost the most money in a single day and SS is that day's loss (ticket cost minus winnings, i.e. Pi−ViP_i - V_i). You may assume grandpa lost money on at least one day. If several days share the maximum single-day loss, print the one with the smallest (earliest) day number.

On the third line print three space-separated integers P1P_1, P2P_2, and SS, meaning that grandpa's most costly period ran from day P1P_1 to day P2P_2, during which his ticket spending exceeded his winnings by a total of SS. If several periods share the maximum total loss, print the one with the smallest starting day P1P_1, and among those the one with the smallest ending day P2P_2.

Examples3

  1. Example 1

    Input
    5
    1 9
    9 0
    3 5
    8 0
    1 9
    
    Expected output
    PLUSSIS
    2 9
    2 4 15
    
  2. Example 2

    Input
    1
    5 0
    
    Expected output
    MIINUSES
    1 5
    1 1 5
    
  3. Example 3

    Input
    3
    100 0
    0 100
    50 50
    
    Expected output
    NULLIS
    1 100
    1 1 100