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
use std::io::{self, Read};

fn next<T: std::str::FromStr>(it: &mut std::str::SplitWhitespace<'_>) -> T {
    it.next().unwrap().parse().ok().unwrap()
}

enum Operation {
    Union(usize, usize),
    Cross(usize, usize),
    Negation(usize),
}

struct Solution {
    operations: Vec<Operation>,
    n: usize,
}

impl Solution {
    fn get_bit(&self, set_id: usize, bit_id: usize, memo: &mut [Option<bool>]) -> bool {
        if set_id <= self.n {
            bit_id % set_id == 0
        } else if let Some(result) = memo[set_id] {
            result
        } else {
            let operation = &self.operations[set_id - self.n - 1];
            let result = match *operation {
                Operation::Negation(a) => !self.get_bit(a, bit_id, memo),
                Operation::Union(a, b) => {
                    self.get_bit(a, bit_id, memo) || self.get_bit(b, bit_id, memo)
                }
                Operation::Cross(a, b) => {
                    self.get_bit(a, bit_id, memo) && self.get_bit(b, bit_id, memo)
                }
            };

            memo[set_id] = Some(result);
            result
        }
    }
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();

    let n: usize = next(&mut it);
    let m: usize = next(&mut it);
    let q: usize = next(&mut it);

    let mut operations: Vec<Operation> = Vec::with_capacity(m);

    for _ in 0..m {
        operations.push(match next(&mut it) {
            1 => Operation::Union(next(&mut it), next(&mut it)),
            2 => Operation::Cross(next(&mut it), next(&mut it)),
            _ => Operation::Negation(next(&mut it)),
        });
    }

    let solution = Solution { operations, n };

    for _ in 0..q {
        let x: usize = next(&mut it);
        let v: usize = next(&mut it);

        let mut memo = vec![None; n + m + 1];
        if solution.get_bit(x, v, &mut memo) {
            println!("TAK");
        } else {
            println!("NIE");
        }
    }
}