Tests for problem D are too ill-conceived: kiimak's told his submission fails on a simple case with n = 5 and here is my dumb solution.

As it was mentioned, we need to check if there is a pair of indices $$$(i, j)$$$ such that $$$a_i$$$ and $$$a_j$$$ intersect but not $$$b_i$$$ and $$$b_j$$$(or vice versa). That is what we do to find those indices:

Perform the following operation 5000 times. Take a randomly generated pivot index not chosen before. This index might be $$$i$$$ in our assumption. Then iterate through $$$[1\dots n]$$$ looking for $$$j$$$. If there is one suitable for us then the answer is NO, we can stop our algorithm. Else try taking another $$$i$$$. This runs in $$$\mathcal{O}(5000 \times n)$$$. Now I'm going to tell why it's a terrible solution and why it mustn't pass the tests(thanks to lemelisk, it's already hacked).

Imagine a test where $$$n = 100000$$$ and there are only two segments intersecting in $$$a$$$ (let their indices be $$$i$$$ and $$$j$$$) and no segments intersecting at all in $$$b$$$. Obviously, the answer is NO, the only suitable pair is $$$(i, j)$$$. What is the probability of picking it? It equals to the probability of picking $$$i$$$ or $$$j$$$ as the pivot index. We pick only $$$\frac{5000}{10^5} = \frac{1}{20} = 0.05$$$ of numbers. So the probability of neither picking $$$i$$$ nor $$$j$$$ is $$$0.95 \times 0.95 = 0.9025$$$. So adding this testcase or the similar one would let my solution fail with a huge probability.

nong, try harder next time!

It's obvious that $$$l = k \cdot x + c$$$, where $$$c$$$ is one of the {$$$a + b, a - b, -a + b, -a - b$$$}(if c < 0, let's increase it by $$$k$$$).

Now we have to find maximum and minimum $$$q > 0$$$ such that $$$q \cdot l \equiv 0$$$(mod $$$n \cdot k$$$).

Finding maximum is quite easy and not really interesting so I will stop on the second problem.

let $$$d = gcd(k, c)$$$. Let's forget about multiplier $$$q$$$, we will add it in formulas a few later.

$$$d \cdot (k' \cdot x + c') \equiv 0$$$(mod $$$n \cdot k$$$)

let $$$rem = \frac{n \cdot k} {gcd(n \cdot k, d)}$$$, $$$x = c' \cdot y$$$(we can choose any $$$x$$$ from $$$[1; \infty]$$$ so let it divide $$$c'$$$)

$$$c' \cdot (k' \cdot y + 1) \equiv 0$$$(mod $$$rem$$$)

Again let $$$rem' = \frac{rem}{gcd(rem, c')}$$$

$$$k' \cdot y + 1 \equiv 0$$$(mod $$$rem'$$$)

If $$$gcd(k', rem') = d' > 1$$$, this equation has no solutions(because $$$k' \cdot y$$$ is multiple by $$$d$$$, and 1 isn't). So our aim is to choose such minimal $$$q$$$ that $$$gcd(k', rem' / s) = 1$$$(choosing $$$s$$$ aliquant by $$$rem'$$$ is meaningless).

To get $$$gcd(k', rem' / s) = 1$$$, we should divide $$$rem'$$$ by all prime $$$p$$$ that divide $$$k'$$$. We can do that in $$$O(\sqrt k')$$$. As $$$k' <= k$$$, total complexity is $$$O(\sqrt k)$$$(or we can use Pollard's p − 1 algorithm and reach $$$O(\sqrt[4]k)$$$