# UVa 10853

## Summary

Develop an efficient method to determine the winner of the game.

## Explanation

The set S of all values of L for which the player A wins can be constructed as follows:

1. ${\displaystyle \{1,2,\dots ,a_{max}\}\in S}$.
2. ${\displaystyle \{u,u+1,\dots ,v\}\in S}$, ${\displaystyle v-u\geq b_{max}-b_{min}}$, and ${\displaystyle u+a_{min}+b_{max}\leq v+a_{max}+b_{min}}$, imply ${\displaystyle \{u+a_{min}+b_{max},\dots ,v+a_{max}+b_{min}\}\in S}$.

A sample solution, based on the above construction:

long long L, amin, amax, bmin, bmax;

char solve()
{
long long d, q;

if (L <= amax)
return 'A';

d = amax - amin + bmin - bmax;
q = (L - 1) / (amin + bmax);

if (d < 0 && q > ((bmax - bmin - amax + d + 1) / d))
return 'B';

return (((L - 1) % (amin + bmax)) < (amax + q * d)) ? 'A' : 'B';
}

## Gotchas

Use 64-bit integers in calculations to avoid overflows.

## Input

4
4 5 7 1 20
5 1 3 1 3
5 2 2 1 3
1000 1 3 1 3


## Output

A
A
B
B