Optimizing Chocolate Selection

Apple loves chocolate but is extremely picky. Its owner wants to give Apple only the chocolates that it will like. Although the owner does not know exactly which type of chocolate Apple prefers, she notices that the cocoa content is an important factor in determining its taste. Specifically, she decides that a chocolate with cocoa content in the interval \([a,b]\) is tasty. However, the ideal interval \([a,b]\) is unknown and she asks for your help to select a range so that Apple gets the maximum possible amount of the chocolates it finds tasty.

The chocolates are categorized by their cocoa content values from \(1\) to \(N\). For each cocoa content \(i\) (\(1 \le i \le N\)), let

[ \begin{cases} pos_i = a_{2i-1} & \text{(number of chocolates that Apple thinks are tasty)}, \ neg_i = a_{2i} & \text{(number of chocolates that Apple thinks are not tasty)} \end{cases} ]

where the sequence \(\{a_i\}\) is generated as follows:

[ a_1\text{ is given, and for } i > 1, \quad a_i = (p_1,a_{i-1} + p_2) \bmod M. ]

Once the owner selects an interval \([a,b]\) (\(1 \le a \le b \le N\)), she considers the chocolates with cocoa content in that range as tasty. Define the following quantities:

[ \begin{cases} TP = \sum_{i=a}^{b} pos_i, & \text{(chocolates both Apple and the owner find tasty)}, \ FN = \sum_{i \notin [a,b]} pos_i, & \text{(chocolates Apple likes but the owner rejects)}, \ FP = \sum_{i=a}^{b} neg_i, & \text{(chocolates Apple dislikes but the owner accepts)}, \ TN = \sum_{i \notin [a,b]} neg_i, & \text{(chocolates both dislike)}. \end{cases} ]

Let the ratio of correctly judged tasty chocolates in Apple’s view be

[ r = \frac{TP}{TP+FN}, ]

and the precision of the owner’s judgment be

[ p = \frac{TP}{TP+FP}. ]

Your task is to choose an interval \([a,b]\) such that the combined measure

[ f = \frac{2pr}{p+r} ]

is maximized.

Note: If there are multiple intervals achieving the same maximum value of \(f\), choose the one with the smallest \(a\) and, if still tied, the smallest \(b\).

inputFormat

The input consists of a single line containing five integers:

\(N\), \(a_1\), \(p_1\), \(p_2\), and \(M\), where \(N\) is the number of cocoa content levels. The sequence \(a_i\) (for \(i=1\) to \(2N\)) is generated by:

[ a_1\text{ is given, and for } i > 1, \quad a_i = (p_1,a_{i-1} + p_2) \bmod M. ]

Then for \(i=1,2,\dots,N\), define:

[ pos_i = a_{2i-1}, \quad neg_i = a_{2i}. ]

You may assume that all input numbers are positive integers and that \(1 \leq N \leq 1000\) (or suitable limits that allow an \(O(N^2)\) solution).

outputFormat

Output two integers \(a\) and \(b\) (with \(1 \le a \le b \le N\)) representing the range \([a,b]\) that maximizes \(f = \frac{2pr}{p+r}\). If multiple intervals yield the same maximum value, output the one with the smallest \(a\); if there is still a tie, choose the one with the smallest \(b\).

sample

3 1 1 1 10

1 3