Cask contrast queries

For each guest sample, find the barrel in a stretch of a winery's cellar that contrasts with it the most.

The cellar has n barrels in a single rack, numbered 1 to n. A stamping machine burned a flavour code into each one: barrel 1 has code seed, and every following barrel has code (previous * mult + add) % mod. A code is a bit pattern in which each bit stands for one tasting note, and more significant bits are more important notes. The contrast between two codes is their bitwise XOR, read as a number.

A guest brings a sample with code x and asks about the barrels numbered l to r inclusive. Among those barrels, find the greatest contrast with x, and name the barrel that provides it. If several barrels give the greatest contrast (their codes are equal), name the one with the smallest number.

Input: n, seed, mult, add, mod, and queries, a list of [l, r, x] with 1 <= l <= r <= n.

Output: a list with one entry [contrast, barrel] per query, in order.

The cellar can hold tens of thousands of barrels and there can be hundreds of questions, so checking every barrel for every question is too slow.