Round-Robin League

In a round-robin league, teams 1 through $n$ play each other exactly once. Each match ends in a win, a loss, or a draw. A win earns $a$ points, a draw earns $b$ points, and a loss earns $c$ points. Unlike the usual scoring in round-robin leagues, the relative order of $a$, $b$, and $c$ is not fixed in this problem. For example, a win may earn fewer points than a loss.

Teams are ranked by points, highest first. If two teams have the same points, the team with the smaller number ranks higher. After all matches end, find the maximum and minimum points that the team ranked $k$th can have.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains $a$, $b$, $c$, $n$, and $k$, separated by spaces.

For each test case, print on one line the maximum and minimum points that the team ranked $k$th can have, in that order.

• $1 \le T \le 100\,000$
• $0 \le a, b, c \le 10^9$
• $1 \le k \le n \le 10^9$