1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// https://sio2.mimuw.edu.pl/c/pa-2026-1/p/grm/
use std::io::{self, BufRead, Write};

fn strategy(request: Request, rounds: &[Round]) -> usize {
    let mut count = request.x;
    let rounds = &rounds[request.l..request.r];

    for round in rounds {
        let mul_amt = round.b as u128 * count as u128;
        let add_amt = round.a as u128 + count as u128;

        count = (mul_amt.max(add_amt) % 1_000_000_007) as usize;
    }

    count
}

#[derive(Clone, Copy, Debug)]
struct Round {
    /// dostać a dodatkowych wojowników
    a: usize,
    /// pomnożyć obecną liczbę wojowników przez b
    b: usize,
}

#[derive(Clone, Copy, Debug)]
struct Request {
    /// po pierwszych l wydarzeniach
    l: usize,
    /// ma x wojowników
    x: usize,
    /// ile będzie miał wojowników po wydarzeniu o numerze r
    r: usize,
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();

    let meta = lines.next().unwrap().unwrap();
    let mut meta = meta.split_whitespace();

    let round_count = meta.next().unwrap().parse::<usize>().unwrap();
    let req_count = meta.next().unwrap().parse::<usize>().unwrap();

    let mut rounds = Vec::with_capacity(round_count);

    for _ in 0..round_count {
        let line = lines.next().unwrap().unwrap();
        let mut line = line.split_whitespace();

        let a = line.next().unwrap().parse::<usize>().unwrap();
        let b = line.next().unwrap().parse::<usize>().unwrap();

        rounds.push(Round { a, b });
    }

    let mut stdout = io::stdout().lock();

    for _ in 0..req_count {
        let req = lines.next().unwrap().unwrap();
        let mut req = req.split_whitespace();

        let x = req.next().unwrap().parse::<usize>().unwrap();
        let l = req.next().unwrap().parse::<usize>().unwrap();
        let r = req.next().unwrap().parse::<usize>().unwrap();

        let req = Request { x, l, r };
        let best_choice = strategy(req, &rounds);

        writeln!(stdout, "{best_choice}").unwrap();
    }

    io::stdout().flush().unwrap();
}