# TopCoder

\begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align}

66.7% (4/6)

11.6% (5/43)

# Description

[1]:
According to popular folklore, many animals are smarter than they appear. Dogs bark before earthquakes; cattle predict rainfall by sitting on the ground. But cattle may have another hidden talent in telling which way is north.
Small animals such as mole rats living underground are known for the use of magnetism to navigate. Dr. Begall and her colleagues wanted to know whether larger mammals also have the ability to perceive magnetic fields. They investigated this possibility by studying images of thousands of cattle captured on Google Earth, a website that stitches together satellite photographs to produce an image of the Earth’s surface.
Grazing animals are known to orient themselves in a way that minimizes wind chill from the north and maximizes the warmth of the sun when they are cold. The researchers therefore had to study a lot of cows grazing in lots of different places at different times of day, in order to average out these factors and see whether cattle could act like compass needles.
The researchers concluded that cattle do generally orient themselves in a north-south direction. This north-south preference has also been noted in flies, termites and honeybees. But unfortunately, even the high resolution of Google Earth is not powerful enough to tell which end of the cow is its head, and which its tail.
The researchers were therefore unable to answer their research questions of whether cattle prefer to look north or south, and whether that differs in the northern and southern hemispheres.

# Input Format

$T\leq 10^ 4; K<N\leq 10^ {19}; A, B\leq 3\times 10^ 9;\gcd(A,B)=1$

 子任務（測資） 額外限制 分數 1 (0~2) $T\leq 2; N,A,B\leq 9$ 6 2 (0~5) $T\leq 2; N\leq 500$ 16 4 (0~8) $T\leq 50; N\leq 10^ 5$ 17 5 (9) $N\leq 100$ 9 6 (0~11) 無限制 52

1
6 1 1 3

32 63

# Problem Source

Problem set / description by Yihda Yol

No. Testdata Range Score
1 0~2 6
2 0~5 16
3 0~8 17
4 9 9
5 0~11 52

# Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1 2 3 5
1 900 65536 262144 1 2 3 5
2 900 65536 262144 1 2 3 5
3 900 65536 262144 2 3 5
4 900 65536 262144 2 3 5
5 900 65536 262144 2 3 5
6 900 65536 262144 3 5
7 900 65536 262144 3 5
8 900 65536 262144 3 5
9 900 65536 262144 4 5
10 100 20480 262144 5
11 100 20480 262144 5