406960: GYM102625 F Basant and the Master Plan

It's $$$Basant$$$, and $$$Sanket$$$ has been searching for a girlfriend from his $$$1^{st}$$$ Year. So this time, he has decided to impress a girl by giving her a $$$Rose$$$.

$$$Roses$$$ can be represented by numbers. From his sources in $$$Rosaline$$$, $$$Sanket$$$ came to know that girls are only impressed by $$$Roses$$$ in which one of the digits is average of all the other digits.

For Example, $$$Rose$$$ number 123, here 2 = $$$\frac{(1+3)}{2}$$$ and contain only specific digits $$$a$$$, $$$b$$$, and $$$c$$$ (Not necessarily all).

Let's call these $$$Roses$$$, Perfect Roses. So, $$$Sanket$$$ went to $$$Hirapur$$$ to buy $$$Roses$$$.

$$$Hirapur$$$ has $$$q$$$ shops ( Numbered 1 to $$$q$$$, as they appear in input ), each shop sells $$$Roses$$$ from number $$$L$$$ to $$$R$$$ (both inclusive). $$$Sanket$$$ is having trouble finding the shop which has the most number of $$$Perfect Roses$$$. Can you help him?

Note 1: 1-Digit numbers (including 0) are not $$$Perfect Roses$$$.

Note 2: Numbers do not contain leading zeros.

The first line of the input contains four integers $$$a$$$, $$$b$$$, $$$c$$$, and $$$q$$$ denoting the digits that the girls like (Not necessarily distinct) and the number of shops in $$$Hirapur$$$, respectively. The description of $$$q$$$ shops follows.

The first and only line of each shop contains two integers $$$L$$$ and $$$R$$$ denoting the range of $$$Roses$$$ the shop sells.

0 $$$\leq$$$ $$$a$$$,$$$b$$$,$$$c$$$ $$$\leq$$$ $$$9$$$

1 $$$\leq$$$ $$$q$$$ $$$\leq$$$ $$$10^5$$$

0 $$$\leq$$$ $$$L$$$ $$$\leq$$$ $$$R$$$ $$$\leq$$$ $$$10^9$$$

In 1 line, print the number of the shop that sells the most number of $$$Perfect Roses$$$. If there are multiple such shops, print the one with the minimum shop number.

1 2 3 2
1 100000000
3 19

1

In the given test case $$$Perfect Roses$$$ can be 11,22,33,111,123,132,213,222,231.....

Shop number 1 sells 1637 $$$Perfect Roses$$$, and Shop number 2 sells only 1 $$$Perfect Rose$$$, so the output is 1.