Nikita and Sasha play a computer game where you have to breed some magical creatures.…
- User
Nikita and Sasha play a computer game where you have to breed some magical creatures. Initially, they have k creatures numbered from 1 to k. Creatures have n different characteristics.
Sasha has a spell that allows to create a new creature from two given creatures. Each of its characteristics will be equal to the maximum of the corresponding characteristics of used creatures. Nikita has a similar spell, but in his spell, each characteristic of the new creature is equal to the minimum of the corresponding characteristics of used creatures. A new creature gets the smallest unused number.
They use their spells and are interested in some characteristics of their new creatures. Help them find out these characteristics. Input
The first line contains integers n, k and q (1 ≤ n ≤ 105, 1 ≤ k ≤ 12, 1 ≤ q ≤ 105) — number of characteristics, creatures and queries.
Next k lines describe original creatures. The line i contains n numbers ai1, ai2, ..., ain (1 ≤ aij ≤ 109) — characteristics of the i-th creature.
Each of the next q lines contains a query. The i-th of these lines contains numbers ti, xi and yi (1 ≤ ti ≤ 3). They denote a query:
- ti = 1 means that Sasha used his spell to the creatures xi and yi.
- ti = 2 means that Nikita used his spell to the creatures xi and yi.
- ti = 3 means that they want to know the yi-th characteristic of the xi-th creature. In this case 1 ≤ yi ≤ n.
It's guaranteed that all creatures' numbers are valid, that means that they are created before any of the queries involving them.
Output
For each query with ti = 3 output the corresponding characteristic.
Examples
Input
2 2 4 1 2 2 1 1 1 2 2 1 2 3 3 1 3 4 2
Output
2 1
Input
5 3 8 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 1 1 2 1 2 3 2 4 5 3 6 1 3 6 2 3 6 3 3 6 4 3 6 5
Output
5 2 2 3 4
Note
In the first sample, Sasha makes a creature with number 3 and characteristics (2, 2). Nikita makes a creature with number 4 and characteristics (1, 1). After that they find out the first characteristic for the creature 3 and the second characteristic for the creature 4.
Assistant
We need to process a series of queries where we can create new creatures from two existing ones using either max or min operations on each of n characteristics. Initially we have k creatures, each with n characteristics (n up to 1e5, k up to 12). q up to 1e5.
We need to answer queries of type 3: given creature x and characteristic y, output the value.
Directly simulating each creation by storing an array of size n for each new creature would be too large: up to q creatures, each with n up to 1e5, so total storage O(n q) could be 1e10.
We need to handle efficiently. Note that k is small (≤12). The operations are max and min over the two parent creatures elementwise. This is reminiscent of operations on vectors under max and min. Since k is small, maybe we can represent each creature as a combination of the original k creatures? Because max and min are idempotent, commutative, associative, and distribute? Not exactly distribution but we can think in terms of bitwise? Actually we have two operations: max (∨ in a lattice) and min (∧). They form a distributive lattice if we consider the natural order. But we're working with values, not just booleans.
Observation: Each characteristic is treated independently: new creature's characteristic j = f(parent1.j, parent2.j) where f is max or min. So all queries are independent across characteristics. However, we have many characteristics (up to 1e5) and many queries (1e5). For each characteristic we need to support dynamic creations of new creatures (via max/min) and queries of value at a given creature. This is reminiscent of building a DAG of operations, and each creature is defined as either an initial constant or f(A, B). Then query asks for value at some node for some dimension j. The total number of nodes (creatures) is up to k+q (since each operation creates a new creature). Actually each type-1/2 query creates a new creature, so total creatures = k + (# of type1/2 queries). Let m = number of type-1/2 queries, m <= q. So total nodes N <= k+q <= 1e5+12? Actually q up to 1e5, so N up to 1e5+12 ~ 1e5. So number of nodes is manageable.
But each node has n characteristics. If we store n values per node, that's too much. However, perhaps we can answer queries offline by processing each characteristic separately? That would require scanning all queries for each characteristic, leading to O(n q) again.
We need a smarter representation. Since k is ≤12, maybe we can represent each creature's characteristics vector as something like: for each subset of original creatures? Or perhaps each creature's characteristic j can be expressed as the maximum (or minimum) of some subset of the original k values? Because the max and min operations applied to initial vectors produce vectors whose each coordinate is either one of the initial values? Let's think: Starting from initial vectors v1,...,vk (each in N^N). When we take max of two vectors, each coordinate becomes max of the two coordinates. Similarly min becomes min. So any creature's characteristic j will always be equal to one of the original k values in that coordinate: a_{i,j} for some i. Because we start with those values and then repeatedly apply max/min which yields values that are among the set of initial values for that coordinate. Indeed, if we have a set S of numbers, and we take max/min of any two numbers from S, we stay within S. So each coordinate's value is always one of the k initial values for that coordinate. So we can represent each creature's characteristic as an index among the original k creatures (i.e., which one's value it equals). But careful: The max of two numbers that are themselves from the set {a1,...,ak} is still one of the numbers from the set, but the specific number depends on the ordering. So indeed, for each coordinate j, the possible values are limited to the multiset (but set) of a_{i,j} for i=1..k. However, note that a_{i,j} may not be distinct; but it's still among those k numbers. So we can compress to an index from 1 to k, but we need to know which original creature's value it equals. But the mapping might not be one-to-one: There could be ties, but max/min will pick one of them, but the actual numeric value may be equal to multiple original creatures. However, if multiple original creatures have the same value for that characteristic, then the index might be ambiguous but the value is the same. So we can represent the resulting value by the actual numeric value, but we could also represent it as a subset? Actually we need to output the numeric value eventually.
Since k is small (≤12), we might represent each creature as a function from the set of original creatures? For each coordinate, the value is equal to the value of some original creature. But which one? It could be determined by which of the original creatures' values are maximum/minimum among the ones present in the ancestors.
Alternatively, we could think of each creature as having a state that is a bitmask of size k indicating which original creatures' values are "dominant"? But operations max/min are monotonic: For max, the resulting value is the maximum among the values of the two parent creatures. If we consider the set of original creatures that could contribute to a given creature's coordinate, maybe it's like: each creature's coordinate equals the maximum (or minimum) value among a subset of the original creatures? Actually yes: Because if we treat each original creature as having its own value for that coordinate. When we combine via max, the result is the maximum of the two values. That is equivalent to taking the maximum over the union of the sets of original creatures that "determine" each parent's value? However, the parents themselves may have values that are not necessarily equal to one specific original creature, but they could be the max over a subset. For example, suppose we have three original creatures A, B, C with values for a coordinate: 5, 3, 1. If we take max(A, B) = max(5,3)=5 which equals A's value. So it's like the max over {A,B} yields A. So it's the maximum value among that subset. Similarly min yields the minimum among the subset. So any creature's coordinate value can be expressed as either the maximum or the minimum over some subset S of original creatures? But note that operations can mix max and min. For instance, we could do max(A, min(B, C)). That yields: min(B,C) = min(3,1)=1; max(5,1)=5 = A. That is again the maximum of some set? Actually it's max(A, min(B,C)). That value is not necessarily equal to either the max or min of a single set? But we can rewrite: max(A, min(B,C)) = ? In a distributive lattice, max distributes over min: max(A, min(B,C)) = min(max(A,B), max(A,C)). So the value equals min( max(A,B), max(A,C) ) = min(5,5)=5. So it's the min of two maxes. So the value can be expressed as a combination of max and min of subsets. In general, the expression formed from the original vectors using max and min is a lattice polynomial. By the properties of distributive lattice, any such polynomial can be written in disjunctive normal form: join (max) of meets (min) of some generators, or meet of joins. But each coordinate's value is a number, not a lattice element from a set of k elements? Actually the set of possible values for the coordinate is the set of numbers a_{i,j}. They form a totally ordered set (since numbers are comparable). In a totally ordered set, max and min correspond to supremum and infimum. And any lattice polynomial on a totally ordered set can be expressed as either the maximum over some set of minima? Actually, any function that is monotone and idempotent? But more concretely, because the set is totally ordered, any expression built from the original variables (k variables) using max and min will output a value equal to one of the variables. And which one it equals is determined by some threshold. In fact, the function is a so-called order statistic: it returns the r-th smallest among the k inputs? Not exactly; the expression can be more complex: e.g., max(min(A,B), C). This yields: if C is large, it might be C; else it's the larger of A and B? Actually min(A,B) is the smaller of A,B; then max with C yields the larger of that smaller and C. That is essentially the second-largest? Let's test with numbers: Suppose A=5, B=4, C=3. Then min(A,B)=4, max(4,3)=4 -> that's B (the middle). With A=5,B=2,C=3: min=2, max(2,3)=3 -> C. With A=1,B=2,C=3: min=1, max(1,3)=3 -> C. So output can be any of the three depending on ordering. But it's still always one of the input values. So for each coordinate j, the expression is a function from the tuple (a_{1,j},...,a_{k,j}) to one of those values. That function is determined solely by the ordering of these k values (since they are numbers, but actual values matter for ties). However, since the values can be arbitrary, the ordering might differ per coordinate. So each creature corresponds to some selection rule: given the k numbers for a coordinate, output one of them based on a formula (the same formula across coordinates). Indeed, because the operations are applied coordinate-wise identically, the same combination of max/min operations is performed on each coordinate. So the creature can be seen as a function f: R^k -> R that is a lattice polynomial (using max/min) and then applied to the k original vectors componentwise. Since the original vectors provide k numbers per coordinate, the result for coordinate j is f(a_{1,j}, a_{2,j}, ..., a_{k,j}).
Therefore, each creature is completely described by a lattice polynomial (expression tree) with leaves being references to original creatures (by number). But note that the leaves are not necessarily the original creatures? Actually the only base creatures are the original k; all later creatures are derived by applying max/min to two previously created creatures. So any creature's value function can be expressed as a lattice polynomial whose leaves are original creatures (1..k). Because the derivation uses previously created creatures, which themselves are polynomials of original creatures. So the overall function is a lattice polynomial over the k variables. Moreover, since we only apply binary max/min, the polynomial can be represented by an expression DAG.
Thus, for each creature x, we can compute a representation of the function f_x: given the k numbers, it returns one of them. Because k is small, we can precompute, for each creature, which original creature's value is selected for each possible ordering? Since the ordering among the k original values determines the outcome. But there are k! possible total orders if values are distinct. However, k ≤ 12, so k! is huge (479M for k=12). Not feasible.
But we don't need to consider all orders; we need to answer queries: for a given creature x and a given characteristic y (i.e., coordinate), we need the actual numeric value. That numeric value is f_x applied to the tuple (a_{1,y}, a_{2,y}, ..., a_{k,y}). So if we can compute f_x efficiently for each coordinate, we could evaluate it for many coordinates. But q up to 1e5, and n up to 1e5. We need to answer up to q type-3 queries, each asking for one coordinate of one creature. So total outputs <= q.
Thus, we can treat each type-3 query as: given a function f (represented by its expression DAG) and a tuple of k numbers (the column y from the initial matrix), compute f applied to that tuple. We need to do this for many queries, each with possibly different functions and different coordinates. Could we preprocess the functions in some way to evaluate quickly for a given tuple? Because the tuple is just the column of the initial matrix, which we know. So we could precompute for each creature and each coordinate the value? That would be N * n, too large.
But maybe we can process queries offline: since queries are interleaved with creations, we need to answer type-3 on the fly? The problem statement: they perform spells and queries in order. So we need to answer as we go. However, we could simulate the process by building the expression trees, and when a type-3 query arrives, we evaluate that creature's function on the specific column. But evaluating the function for a given coordinate might require traversing the DAG, which could be deep (up to N). If we evaluate each query by traversing the DAG, that would be O(depth) per query. Depth could be O(N) in worst case (linear chain). But N up to 1e5, q up to 1e5, so O(N q) worst-case 1e10, too slow. But maybe depth is not too high? It could be linear because each creation uses two earlier creatures, so the DAG could be a binary tree, depth up to N. So we need faster evaluation.
Observation: Since the functions are lattice polynomials over k variables, we could represent them in a more compact form using bitmasks. Because the output for a given tuple (v1,...,vk) depends only on the relative order of the vi. However, evaluating a lattice polynomial can be done by noting that max corresponds to taking bitwise OR of some representation, and min to AND? If we think of the k values as sorted, maybe we can represent the function as a subset of the set of original indices that are "acceptable"? Let's explore.
Consider that each original creature i gives a value vi (for a fixed coordinate). We want to compute f(v1,...,vk). Since f is a lattice polynomial (using max and min), it is monotone non-decreasing in each argument? Actually max and min are both monotone: max is increasing in both arguments; min is increasing in both arguments as well? For min, if you increase one argument, the min can either increase or stay the same, but it's non-decreasing: min(a,b) <= min(a',b) if a <= a'. So yes, both max and min are monotone non-decreasing (isotone) in each argument. So f is isotone. Also, f is idempotent: f(t,t,...,t)=t. These are called "lattice polynomials" or "order-preserving homogeneous functions". For a totally ordered set, any such function can be expressed as either the r-th order statistic for some r? Not exactly, e.g., max(min(A,B), C) is not an order statistic? Actually order statistics are: given k numbers, pick the r-th smallest. For k=3, order statistics are min, median, max. But max(min(A,B), C) is not necessarily median; as seen earlier it can be max, min, or median depending on values. Wait but for any particular fixed input, it returns one of the values. However, as a function, it is not a fixed order statistic for all inputs; it changes which rank it picks based on the input. For example, for A=5,B=4,C=3, it returns 4 (the middle). For A=5,B=2,C=3, it returns 3 (which is max? Actually max is 5, min is 2, 3 is middle). For A=1,B=2,C=3, returns 3 (max). So the rank of output varies. So it's not a simple order statistic.
But maybe we can represent f as a combination of thresholds using the concept of "monotone Boolean functions"? Because if we fix a threshold T, compare each vi against T. Since f is monotone, we can decide f(v) >= T? This is typical for analyzing functions over a totally ordered set. For each possible value (from the set of a_{i,j}), we could evaluate f by looking at which inputs are >= that value. However, there are many possible values (up to k per coordinate, but they can be up to 1e9). But maybe we can use the fact that there are only k distinct values per coordinate (but they could be less). Actually each coordinate j has exactly k numbers (from original creatures) but they may not be distinct. So there are at most k distinct values per coordinate. So we could, for each creature, precompute for each coordinate a mapping from the sorted order? But again n is large.
Given small k, we might think of each creature's function as a Boolean function on k bits? Consider the following: For a fixed coordinate, suppose we label the original values and sort them. But the function's output is one of those values. Could we decide the output by comparing the values? Since k is ≤12, we can evaluate f on the fly for a given tuple by plugging the numbers into the expression tree. That would take time proportional to the size of the tree (number of operations). But we have many queries (maybe up to 1e5) each possibly on different creatures, and the tree could be large. However, we can precompute for each node (creature) its "function" in a form that allows fast evaluation per tuple. Since k is small, we can represent the function as a lookup table over all subsets? Actually the function's output is determined by the ordering of the k values. The number of possible total orders (permutations) is k! which is huge for k=12 (479M). But perhaps we can represent it as a decision tree or as a Boolean formula? Another direction: Since we only need to evaluate for specific tuples (the columns of the initial matrix), and the initial matrix is fixed, we could preprocess each column (i.e., each characteristic) by sorting the original k values? That might help evaluate many functions for the same column.
Alternate approach: Instead of building functions, we could simulate the process but compress the representation per creature using bitmasks. For each creature, we can compute, for each characteristic j, the index of the original creature whose value it takes. That would be N * n, too big. But note that n is up to 1e5, N up to 1e5. However, q (type-3 queries) is only up to 1e5. So we don't need to know all characteristics for all creatures; we only need to answer queries as they come. So we could compute the answer for a query by recursively combining the parents' values for that characteristic. But that would involve recursion depth potentially large. Could we use memoization/dynamic programming to compute the answer for each creature-characteristic pair only when needed? Since each query asks for a specific creature and characteristic, we could compute it on demand and cache the result (since there might be multiple queries for same creature and characteristic). In worst case, we could have q distinct (creature, characteristic) pairs, each requiring computation. If each computation costs O(depth), worst-case O(q * depth) could be high. But depth could be up to N, and q up to 1e5, so 1e10. However, maybe we can compute each creature's value for a characteristic in O(1) after preprocessing something like "representative" for each creature? But maybe depth is not that high on average? But we need guarantee.
We need a more efficient method.
Given that k is at most 12, we might try to compute for each creature a bitmask of size k that captures the function sufficiently to evaluate it for any given tuple of values. How? Let's think in terms of "for each original creature i, what is the condition under which the output equals or exceeds its value?" Or we can compute the output as the maximum over some set of minima? Actually any lattice polynomial can be written in disjunctive normal form as: f(x) = max_{S in F} min_{i in S} x_i, where F is a family of subsets of {1..k}. This representation is as a join of meets. Similarly it can be written as a meet of joins. Since the lattice is distributive, such representation exists. Moreover, because the operations are max and min, the expression can be reduced to such a form. For a polynomial that uses both max and min, it can be represented as max over some min-terms. The set F is an antichain of subsets (if simplified). Similarly, we could represent it as min over some max-terms.
Thus, each creature corresponds to a family F of subsets (or a single Boolean function). The output for a given tuple (v1,...,vk) is max over subsets S in F of min_{i in S} v_i. Since each min_{i in S} v_i is the minimum value among those in S. Then the max over these minima picks the largest such minimum. Equivalently, we can think: f(v) = the largest value t such that there exists a subset S in F with min_{i in S} v_i >= t. Or also, t = max_{S in F} (min_{i in S} v_i). This is reminiscent of the concept of a "blocker" or "hitting set".
Now, if we have such a family F for each creature, we could evaluate f on a given tuple quickly: we need to compute for each S in F the minimum of v_i for i in S, and then take max. But the family F could be large; potentially exponential in k. But since k is small (12), the number of possible subsets is 2^k = up to 4096. So it's feasible to store a bitmask representation as a Boolean function over k variables, e.g., a monotone DNF with clauses being subsets. The size of the family F (the set of minimal subsets) could be at most the number of antichains, which is still possibly exponential (the Dedekind number), but for k=12 it's huge ( > 10^6?). Actually number of antichains (or monotone Boolean functions) for k=12 is around 10^13? Wait, the Dedekind numbers: D(0)=2, D(1)=3, D(2)=6, D(3)=20, D(4)=168, D(5)=7581, D(6)=7,828,354, ... D(8) is huge. So for k=12, it's astronomically large. However, our expressions are built from binary operations; the family F representing a particular polynomial may not be arbitrarily complex; its size could be exponential in the number of operations? Possibly, because combining two functions via max or min can multiply the number of min-terms. For example, the expression (a1 ∧ a2) ∨ (a3 ∧ a4) ∨ ... etc. But with k=12, the maximum number of min-terms in a reduced DNF is limited by the number of possible subsets (2^k). In worst-case, a function could have all subsets of size floor(k/2) as min-terms, which would be huge (C(12,6)=924). That's manageable! Actually the number of subsets of size up to k is 2^k = 4096. So the maximum number of min-terms (prime implicants) is at most 2^{k-1}? But in monotone DNF, each min-term is a set. The total number of possible distinct min-terms is 2^k-1 (excluding empty). So at most 4095 min-terms. That's not huge. So representing a function as a set of subsets (or a bitmask of which subsets are present) is feasible? 4095 is okay. But there could be many creatures (up to 1e5), each storing up to 4095 subsets, that would be huge: 1e5 * 4095 ≈ 4e8, maybe borderline but memory might be high (each subset could be a 12-bit mask, storing as 16-bit int, so 4e8 * 2 bytes = 800 MB, too much). But not all functions will have that many min-terms; maybe typical ones are simpler. However, we need a guaranteed solution.
Alternative: Since k is only up to 12, we could represent each function by its truth table over all 2^k possible input patterns? But the input is not Boolean; we need to evaluate on numeric values. However, the output is one of the k numeric values. We could precompute for each creature a ranking function that given the ordering of the k numbers (i.e., a permutation) returns the index of the selected value. The number of possible permutations is k! which for k=12 is 479M, too large.
But we could evaluate f(v) by simulating the expression tree, but we need to speed up many evaluations across many coordinates. Since n (number of characteristics) is up to 1e5, and we have up to 1e5 queries, we could preprocess the initial data: For each characteristic j, we have a tuple of k numbers. We could sort the indices by value, or compute the sorted order. Then evaluating f(v) reduces to: given the sorted order of the k values for that characteristic, which index does f pick? This might be determined by some threshold: f chooses the maximum over minima of subsets. We could compute the value by scanning through the sorted values from highest to lowest, checking if there exists a subset S in F such that all indices in S have value >= current candidate. That would be like: find the largest t among the distinct values such that the set of indices with value >= t contains some subset in F. More precisely, f(v) = max_{S in F} min_{i in S} v_i. If we sort the values descending, we can test membership in F. This suggests that we could precompute, for each creature, the family F (as a set of bitmasks). Then for a given column's tuple, we can compute f(v) by iterating over subsets in F? But number of subsets could be up to 4095, and we'd do that per query, so worst-case 4095 * 1e5 = 4e8, maybe acceptable? 4e8 operations might be borderline but possible in C++ with optimization? 400 million simple operations might pass within 2 seconds? Possibly borderline. But memory for storing F for each creature could be high: if each creature stores a list of subsets (bitmask integers) with average length maybe moderate. However, worst-case could be many creatures each with many subsets; but maybe we can bound the total size because each creation operation combines two functions via max or min, which can increase the number of min-terms, but could also simplify? We need to analyze the maximum possible number of min-terms for a function derived from binary max/min on k variables. Since each operation (max, min) corresponds to join (OR) and meet (AND) in the lattice of monotone Boolean functions? Actually not exactly, but there is a connection: If we treat the function f as mapping from the Boolean cube? Hmm.
Alternatively, we can represent each function as a bitmask of size 2^k? That would be 4096 bits = 512 bytes per creature. For 1e5 creatures, that's 51 MB, which is acceptable! Indeed, we can represent the function's behavior for all subsets? How? Let's consider the concept of "upward closed sets". For monotone Boolean functions, we often represent by the set of minimal true inputs (or maximal false). But to evaluate f(v) we need more than Boolean; we need the numeric output. However, perhaps we can transform the problem into evaluating a monotone Boolean function for each threshold. Because f(v) >= t is a monotone Boolean condition: it's true iff there exists S in F such that for all i in S, v_i >= t. That is exactly the condition that the set of indices i with v_i >= t contains some subset S from F. Equivalently, if we define a monotone Boolean function g on k variables where the variables indicate whether v_i >= t. Then f(v) >= t iff g(X_t)=1, where X_t = {i | v_i >= t}. So f(v) is the maximum t such that g(X_t)=1. Since the possible t are exactly the values a_{i,j} (maybe plus something), we can determine f(v) by binary search on the sorted distinct values of the tuple, checking g(X_t). And g is exactly the monotone Boolean function corresponding to the lattice polynomial f (with max/min replaced by OR/AND if we treat threshold). Indeed, if we replace each numeric value by a Boolean indicating >= t, then max corresponds to OR? Let's check: For two Boolean values b1,b2 (0/1), max(b1,b2) as numbers: if we treat true=1, false=0, max(b1,b2) = b1 OR b2. Similarly, min(b1,b2) = b1 AND b2. So thresholding transforms the max/min operations into Boolean OR/AND operations. So for a fixed threshold t, the Boolean value of (f(v) >= t) can be computed by the same expression tree but with leaves replaced by (v_i >= t). So each creature defines a monotone Boolean function g_t (which is the same for all t, because the expression structure is the same, just the leaf values become Booleans based on comparing the original v_i to t). So essentially, each creature corresponds to a fixed monotone Boolean function g (on k Boolean inputs) that does not depend on t. Indeed, if we replace each leaf (original creature i) by a Boolean variable x_i = (v_i >= t), then the expression using OR (for max) and AND (for min) yields a Boolean result that is exactly (f(v) >= t). So g is the Boolean function derived from the same expression but with OR/AND instead of max/min. This g is a monotone Boolean function (since OR and AND are monotone). So each creature can be represented by a monotone Boolean function on k variables.
Now, to compute f(v) for a given tuple v (the column values), we need to find the largest t among the set {v_i} such that g(X_t) = 1, where X_t is the bitmask of indices i with v_i >= t. Since the values are from the set of v_i (maybe not distinct), the answer is one of those v_i. We can find it by iterating over the distinct values in descending order, but that could be up to k per query. k <= 12, so we can just sort the values descending and test g on each prefix. So per query, we would need to evaluate g on up to k different bitmasks (one for each threshold). And evaluating g given a bitmask of size k can be done quickly if we have a representation of g that allows O(1) or O(something small) evaluation.
Thus, the problem reduces to: maintain a collection of monotone Boolean functions (on k variables) as we build them via OR/AND of two existing functions (since type1 corresponds to OR, type2 corresponds to AND). For each function, we need to be able to evaluate it on a given bitmask (size k) quickly (preferably O(1) or O(k)). And we have up to 1e5 functions (creatures), each created by either being an initial leaf (creature i: its function is just the variable x_i? Actually initial creature i: if we ask its characteristic, it's just a_i,j. But if we treat its Boolean function g for thresholding, then for the i-th original creature, f_i(v) = v_i. So its threshold condition is (v_i >= t) i.e., g_i(X) = 1 iff (i in X). So that's the projection function: g_i(X) = x_i. That's a monotone Boolean function (a single variable). So initial functions are just single-variable indicators.
When we create new creature via Sasha's spell (type1 = max), the Boolean function is g_new = g_A OR g_B (since max corresponds to OR for threshold). For Nikita's spell (type2 = min), g_new = g_A AND g_B.
Thus, we have a dynamic process: we start with k initial functions (each is a literal). Then we perform m operations, each creating a new function as OR or AND of two existing functions. We also have queries of type 3: given a function (represented by creature number x) and a characteristic y (i.e., a specific column), we need to compute f_x(v_y) where v_y is the tuple (a_{1,y}, ..., a_{k,y}). We can compute it using the associated Boolean function g_x: f_x(v) = max_{t in values} { t | g_x( {i | a_{i,y} >= t} ) = 1 }. Since the set of possible t are exactly the a_{i,y} values (maybe plus something if ties). But we can equivalently compute: sort the k values descending: let sorted list be w1 >= w2 >= ... >= wk (with indices accordingly). Then for each rank r from 1 to k, consider threshold t = w_r, the set X_t includes indices whose value >= w_r, which is precisely the set of indices of the first r values (assuming distinct; if ties, we need careful: if equal values, then threshold equal to that value will include all with value >= that value, which may be more than r if duplicates. But we can handle by grouping equal values. However, since we are taking maximum t such that condition holds, we can test thresholds at each distinct value. Since k is small, we can just iterate over all k values, compute the mask for ">= current value", evaluate g_x, and keep the max t where true. That works even with duplicates: if values equal, then the same t may appear multiple times, but the condition will be true for the same t, and we'll get the same t. So we can simply iterate over i from 1..k, let mask = bitmask of indices j such that a_{j,y} >= a_{i,y}. Compute g_x(mask); if true, answer = max(answer, a_{i,y}). Since we take max over all i where g_x(mask) true. Complexity: O(k) per query, plus evaluation of g_x(mask). If evaluation is O(1), total O(k) per query = ~12 operations, great.
Thus, the core problem is to maintain a set of monotone Boolean functions on k variables (k ≤ 12) under OR and AND operations (binary), and support evaluation on a given bitmask (size up to 2^k). We have up to 1e5 creations and up to 1e5 evaluations. We need to store these functions efficiently and answer quickly.
Given k ≤ 12, we can represent a Boolean function by its truth table over all 2^k possible inputs. That's 2^k bits = 4096 bits = 512 bytes. With N up to 1e5, that's 100k * 512 bytes = 51.2 MB, which is acceptable in memory. Each operation (OR/AND of two functions) can be done by bitwise OR/AND on the truth table bits. Since we have 4096 bits, we can represent as an array of 64-bit integers: 4096/64 = 64 words. So each function can be stored as an array of 64 uint64_t. Then OR/AND is just loop over 64 words doing bitwise OR/AND, which is O(64) per operation, very fast. Evaluations: given a mask (0..2^k-1) we need to look up the bit at that position. That can be done by computing which word and which bit. So O(1). Perfect!
But wait: The truth table of a monotone Boolean function is not arbitrary: it's monotone. However, our operations OR/AND of monotone functions will produce monotone functions, but we don't need to enforce monotonicity; we can just compute truth tables for the derived functions using the operations on the leaf functions (which are variables). Since leaf functions are projection: f_i(mask) = (mask >> i) & 1? But careful: mask representation: we need to decide a mapping from subsets of {1..k} to bit indices. Typically, we can use bitmask of size k: mask has bit i set if x_i = 1 (i.e., v_i >= t). Then the Boolean function g takes mask as input and outputs 0/1. So we can store truth table over all 2^k masks. For initial function for original creature i, we need g_i(mask) = 1 iff bit i is set. That's a specific truth table. For each derived function, we combine truth tables by bitwise OR or AND. However, note: When we do g_new = g_A OR g_B, the OR is over the output values for each input mask, not bitwise OR on masks. So we need to compute g_new(mask) = g_A(mask) OR g_B(mask) for each mask. This is indeed a pointwise OR across the truth table. Representing the truth table as a bitset where each bit corresponds to a mask, we can do bitwise OR on the whole bitset if we store the bits such that the bit for mask m is set if g(m)=1. Then g_A OR g_B corresponds to bitwise OR of the two bitsets. Similarly, AND corresponds to bitwise AND. So yes.
Thus, we can maintain for each creature a bitset of size 2^k (call it B). Then creation of new creature via type1: B_new = B_x | B_y; type2: B_new = B_x & B_y.
We then answer type3: given creature x and characteristic y, we have the column values a[1..k][y]. We need to compute f_x(v). Steps:
- Build a list of pairs (value, index) for that column: for i in 1..k: value = a[i][y]. We'll have at most k entries.
- Sort these pairs descending by value. But we also need to compute masks for thresholds. Alternatively, we can precompute for each characteristic y a sorted list of indices by value, and also precompute the mask for each prefix? Since k ≤12, we can just compute on the fly per query.
Simplest: For each query, we iterate i from 1..k, but we need to compute mask for ">= a[i][y]". That mask can be computed by scanning all k indices and including those with value >= current threshold. Since k ≤12, O(k^2) per query (i.e., 144) is fine. But we can also precompute for each characteristic the list of values sorted and the corresponding cumulative mask. Since n could be up to 1e5 and we have up to 1e5 queries, we could precompute for all characteristics the sorted order and masks. That would take O(n * k log k) time to sort each characteristic's k values, which is n12log12 ≈ 1e5124 = 4.8e6, acceptable. And memory: for each characteristic we need to store the sorted values and maybe cumulative masks. But storing an array of size nk (1e512) for values is okay (1.2e6 numbers). Additionally, we might need to store masks (12 per char). So that's fine. However, we can also compute on the fly per query: O(k log k) sorting of 12 items is trivial. Since q up to 1e5, that's at most 1e5 * (12 log 12) ~ 5e6 operations, also fine. So we can just compute per query.
But careful: The initial data: k lines each with n numbers. So we have a matrix a[k][n]. That's kn ≤ 121e5 = 1.2e6, which fits. We can store that as, say, vector<vector> a(k, vector(n)). So we can access a[i-1][y-1] quickly.
Now, for each query type 3:
- Let creature index = x (1-indexed). We have its truth table bitset B[x] (stored as an array of 64-bit words).
- Let characteristic index = y (1-indexed).
- Build an array of pairs: for each i from 0 to k-1: value = a[i][y-1], index = i.
- Sort descending by value. If equal values, we need to treat correctly: for threshold equal to that value, the set includes all indices with value >= that value, which includes all indices with that value. So if we iterate over the sorted list, we can maintain a current mask. Starting from the largest value, we add indices to mask as we go. For each distinct value (or each step) we can evaluate g_x(mask). Since we want the maximum value where g_x(mask) true, we can iterate through sorted values and after adding each index (or group) evaluate; if true, update answer to current value. Since we process in descending order, the first time we get true, that value is the maximum. However, we must be careful: if after adding a group of equal values, g_x becomes true, then the answer is that value. But if g_x becomes true only after adding some later lower value, then answer is that lower value. So we can just scan descending and break when true (since we want max, we can break at first true). But wait: Suppose for mask after adding some indices, g_x is false; but after adding more indices (lower values), g_x becomes true. That would mean the maximum t that yields true is the value at that later step, because for higher thresholds (i.e., larger t) the mask is smaller (only indices with value >= larger t). Since we are scanning from high to low, the mask grows. So g_x may flip from false to true at some threshold. The highest t for which it's true is the first value (in descending order) at which g_x becomes true. But careful: if g_x is true for the initial empty mask? That would correspond to threshold greater than all values? But we only consider thresholds that are actual values. So the mask for threshold > max is empty. But the function g_x applied to empty mask: could it be true? That would mean f_x(v) >= t for t greater than max(v_i) is false because no value can exceed max. However, from the Boolean perspective, if g_x(empty) = 1, that would indicate f_x(v) >= t for t > max(v_i) would be true, which is impossible because f_x(v) is one of the v_i. But is it possible for the Boolean function derived from a lattice polynomial to output 1 on empty set? Let's examine: For initial leaf function g_i(mask) = (i in mask). For empty mask, it's false. For any combination of AND and OR, starting from these, the result on empty mask will always be false? Because AND of any false with anything is false; OR of all false is false. So indeed, g(empty) = 0 for all functions derived from these leaves via AND/OR. So we don't need to worry. So scanning works.
Thus algorithm:
- Read n, k, q.
- Read the matrix a: k rows, each with n ints.
- We'll have an array of creatures, initially indices 1..k. For each i from 1..k, we compute its bitset representation B[i] as the truth table of the variable x_{i-1} (since indices 0-based). For each mask from 0 to (1<<k)-1, B[i][mask] = ((mask >> (i-1)) & 1). But we can compute B[i] efficiently without iterating over all masks: we can compute a formula. Since we store bitset as an array of words, we need to set bits for all masks where that bit is set. There's a known pattern: for a single variable, the truth table is: bit at mask is 1 iff the i-th bit of mask is 1. So we can generate B[i] by iterating over masks or using bit operations. Since 2^k = up to 4096, we can simply loop over masks for each initial creature: 12 * 4096 = 49152 operations, trivial.
Alternatively, we can precompute B[i] using a DP: For each mask, we can derive quickly. But brute force is fine.
- We'll also need to store B for each new creature. Since total creatures N = k + (#type1/2) ≤ k+q ≤ 100012, we need to store up to 100k bitsets, each 512 bytes → about 51 MB. Acceptable. However, each bitset is 4096 bits; storing as 64 uint64_t uses 864=512 bytes. 100k512 = 51.2 MB. In C++ this is okay within typical memory limits (256 MB or 512 MB). But we need to be careful with overhead of vector of vectors. We can store as vector<bitset<4096>>? But std::bitset<4096> is a fixed-size template, but 4096 is not a constant? Actually it can be a constant if k ≤ 12, then 1<<k up to 4096. But k is variable (≤12). We can't use bitset with dynamic size; we need to use bitset with size determined at compile time? We could use std::bitset<4096> always (since max is 4096). That's fine. Then each bitset is 4096 bits (512 bytes). Overhead minimal. So we can have vector<bitset<1<<12>> maybe. But 1<<12 = 4096, we can use bitset<4096>. However, note that if k < 12, the truth table still has 2^k entries but we would have extra bits that are unused. That's okay; we just ignore them. But careful: When we combine bitsets via OR/AND, the unused bits (with mask >= 2^k) would also be combined, but they are always zero if we initialize properly? We'll only set bits for masks < (1<<k). For masks beyond 2^k -1, they are not used; we can ensure they remain 0. If we use bitset<4096> and k=12, exactly 4096 bits; if k<12, we only consider masks from 0 to (1<<k)-1; bits beyond that should be 0 and never accessed. When we evaluate g(mask), mask will always be less than (1<<k) because mask is built from k bits; it's at most (1<<k)-1. So fine. So we can use std::bitset<4096> for all.
But 4096 bits is 512 bytes, and 100k of them is 51.2 MB, which is okay. However, std::bitset<4096> might have some overhead? Typically it's just an array of unsigned long; size is 512 bytes exactly. So vector<bitset<4096>> of size 100k would be about 51 MB plus vector overhead (8 bytes per element) = ~0.8 MB, still fine.
Alternatively, we can store as array of 64-bit words and manually manage to reduce memory if needed, but this is simpler.
Now, each creation: type1: B_new = B[xi] | B[yi]; type2: B_new = B[xi] & B[yi]. We then push back new bitset to the vector.
Now answer type3: For creature x, characteristic y:
- Let mask = 0 initially.
- We need to get the sorted list of (value, idx) for column y. We'll create a vector of pairs: for i from 0 to k-1: val = a[i][y-1]; idx = i. Sort descending by val.
- Iterate through sorted pairs; maintain mask = mask | (1 << idx). But if there are equal values, we should include all indices with the same value together to ensure we test the mask that includes all >= that value. Since we are scanning descending, we can group equal values: while next has same value, add to mask? Actually simpler: after sorting, we can iterate i from 0 to k-1, and at each step, set mask |= (1 << idx_i). Then if B[x][mask] is true, then answer = val_i (since this is the current value). But careful: Suppose we have equal values: For instance, values: 5,5,4. Sorted: first idx with 5, we update mask to include that index, evaluate B[mask] for mask containing only that index (maybe both 5's not yet included). But is that the correct threshold? The threshold t = 5. For t=5, the set of indices with value >=5 includes all indices with value 5. So the mask should include both indices with value 5. If we test after adding only the first 5, we might get a false negative or false positive. Let's see: If the function requires both 5's to be present to be true, then after adding only one, B[mask] might be false; but after adding the second 5, it becomes true, and we would get true at the second iteration with same value 5. If we then set answer = 5 (the current value), that's correct. However, if we break at first true, we might break after the second 5, still value 5. But what if the function becomes true only after adding both 5's? With our stepwise approach, after adding the first 5 we test false, after adding second 5 we test true and set answer=5. Good. But what if the function becomes true only after adding a 4? Then answer becomes 4. So the stepwise approach works if we test after each addition, even for equal values. However, we need to ensure we don't miss the case where the function is true for mask with only some of the equal-valued indices but not all? Could that happen? Let's think: For threshold t = 5, the mask is all indices with value >=5, i.e., both 5's. So if the function is true for a subset that does not include both 5's but still satisfies the condition for t=5, is that possible? Condition for t is that there exists S in F such that all i in S have value >= t. If we only have one 5 included, but the other 5's value is also >=5, but the mask we use for threshold t=5 should include all indices with value >=5, by definition. So we cannot have a mask that includes only some of the indices with value exactly 5 if we are considering threshold exactly 5, because those indices also satisfy >=5. So the correct mask for t=5 includes all such indices. So evaluating on a mask that only includes a subset of those indices could give a different result, possibly true when the true condition would be false, or vice versa. For example, suppose the function g requires at least one index from the set of indices with value >=5, but not necessarily all. Then g(mask) where mask includes only one of the two 5's is true, and g(mask_all) also true. So no problem. But if g requires both 5's to be present (i.e., conjunction), then g(mask) with only one 5 is false, but g(mask_all) is true. So we need to test the correct mask, which includes all indices with value >= t. Therefore, we must ensure that for each distinct threshold value, we test the mask that includes all indices with value >= that threshold. With stepwise addition, if we test after each individual index, we might test a mask that does not yet include all indices with the current value (if there are more indices with same value later). That could lead to incorrectly concluding false for t when actually it's true, if the function requires all those indices. However, would that ever lead to an incorrect answer? Let's simulate: Values: 5 (idx1), 5 (idx2), 4 (idx3). Suppose g requires both idx1 and idx2 to be present. For t=5, the correct mask includes both idx1 and idx2. Our stepwise: after idx1, mask = {idx1}, test -> false. after idx2, mask = {idx1, idx2}, test -> true, and value=5. So we set answer=5 (correct). Now suppose g requires idx1 and idx2 and idx3? That's impossible for t=5 because idx3 is not >=5, but anyway. So stepwise works because we eventually test the full mask for t=5 before moving to lower values. However, what if we break at first true? After idx2 we get true and break, answer=5 correct. So it's okay.
But consider a scenario where the function is true for mask that includes only idx1 but not idx2, and false for mask that includes both? Is that possible for a monotone Boolean function? Monotone means if mask1 ⊆ mask2 and g(mask1)=1 then g(mask2)=1. So if g({idx1})=1 then g({idx1,idx2}) must be 1. So it's not possible for g to be true for a subset and false for a superset. So if g is true for the mask with only one of the equal-valued indices, it will also be true for the full mask. So if we test after adding the first index and get true, we could break and answer the current value (which is 5). That is correct because for threshold t=5, the correct mask (full) is a superset of the mask we tested, so if g is monotone, true on subset implies true on superset. Wait, monotonicity: if g(A)=1 and A ⊆ B, then g(B)=1. So if we test a mask that is a subset of the correct mask (because we haven't added all indices with that value yet) and get true, then the correct mask would also be true. So the maximum threshold for which g is true is at least this value, and we can safely set answer to the current value and break. But careful: The current value is 5, but the mask we tested is missing some indices with value 5. However, because the correct mask (including all >=5) is a superset, monotonicity ensures it's also true. So it's safe to conclude that f(v) >= 5. But could it be that f(v) is actually >5? No, because 5 is the maximum value among v_i; so f(v) cannot exceed max, but it could equal max. So answer would be 5, correct. So even if we break early on a subset, we still get correct maximum value because monotonicity guarantees that if any subset of the >=t set yields true, then the full set yields true. However, we must ensure that we are testing the condition for threshold exactly t? Let's think: The condition for f(v) >= t is g( {i | v_i >= t} ) = 1. That's the condition for the full set. If we test a subset S of that full set and get g(S)=1, by monotonicity we have g(full)=1. So the condition holds. Therefore, if we find any mask (which is built incrementally) for which g is true at a certain value, then we know that for the threshold corresponding to that value, the full set also yields true. So we can answer that value. But wait: we need to ensure that the mask we test corresponds to a threshold at least as large as the value? The incremental building: we start from highest value, and as we add indices, the current value is the value of the last added index. At that point, the mask includes all indices we have added so far, which are exactly those with value >= current value? Not necessarily: because if there are other indices with the same value that we haven't added yet (since we add one by one), the mask does not yet include all indices with value >= current value if there are more indices with that same value. However, the mask we have is a subset of the full set for threshold current value. So if g(mask)=1, then by monotonicity g(full) =1, so f(v) >= current value. So it's safe. But could it be that g(mask)=1 for some mask that is not a superset of the full set for any threshold? Actually the mask we test at each step is the set of indices processed so far, which is exactly the set of indices with value >= some threshold? Not exactly: Suppose values: 5 (idx1), 4 (idx2), 3 (idx3). Sorted: idx1 (5), idx2 (4), idx3 (3). After adding idx1, mask = {idx1}. This is exactly the set of indices with value >=5? That's correct because only idx1 has value >=5. After adding idx2, mask = {idx1, idx2}. This is exactly the set with value >=4? Yes, because both have value >=4. After adding idx3, mask = all three, set with value >=3. So for distinct values, the mask after each addition exactly corresponds to the set for threshold equal to the current value. If there are duplicates, after adding the first of the duplicates, mask does NOT correspond to any threshold set, because threshold equal to that value would include all duplicates. But monotonicity ensures that if g(mask)=1 at that point, then the full set (including other duplicates) also yields true. So the condition for threshold equal to that value holds. However, it's also possible that g(mask)=1 only after adding some duplicates but not all, and later adding more duplicates still yields true. So we will eventually see true at that value. If we break as soon as we see true (even on a subset), we may break earlier than the point where we have processed all duplicates, but that's fine because the condition for the threshold (value) holds. However, there is a subtlety: Suppose we have duplicates: values: 5 (idx1), 5 (idx2). Sorted: idx1 (5), idx2 (5). After adding idx1, mask = {idx1}. If g({idx1}) = 1, then we break and answer 5. This is correct because f(v) >= 5 holds (since full set {idx1,idx2} also yields true). If g({idx1})=0 but g({idx1,idx2})=1, then we will not break at first, we will add idx2, then test and break, answer 5. So correct.
Thus, we can simply iterate through sorted indices (by value descending), maintain mask (OR bits as we go), test g(mask) after each update, and if true, output current value and break. This yields O(k) tests per query. Since k <= 12, that's fine.
But we must be careful about sorting stable? We'll just sort pairs by value descending; if values equal, order doesn't matter because we add them one by one; monotonicity ensures correctness as argued. So algorithm is sound.
Now, we need to compute B[x][mask] quickly. With std::bitset<4096>, we can test B[x].test(mask). That's O(1) (bit access). So per query we do up to 12 such tests.
Now, we must also handle the creation of new creatures. For each type 1/2 query, we compute new bitset by bitwise OR or AND of the two parents' bitsets. With bitset, that's just B_new = B[x] | B[y]; etc. So creation O(2^k / word_size) ~ 64 operations, which is trivial.
Thus total time: O((k + q) * (2^k / 64) for creations? Actually creations: each creation does one bitset operation, each bitset operation is O(2^k / wordsize) = O(4096/64)=64 simple bit ops, times up to q (1e5) = 6.4e6 ops. Plus for each type3 query: O(k log k) to sort (12 log 12 ~ 50) plus O(k) tests (12). So total ~1e5 * 50 = 5e6. Plus reading input, etc. So overall well within limits.
Memory: store matrix a: k * n ints. k up to 12, n up to 1e5 => 1.2e6 ints ~ 4.8 MB. Plus bitsets for creatures: up to (k+q) * 512 bytes. But note that q includes both creation and query; but we only create new creatures for type1/2; for type3 we don't create. So number of creatures = k + (#type1/2). In worst case all q are type1/2, so creatures = k+q <= 100012. So bitsets = ~51 MB. Plus vector overhead: storing as vector<bitset<4096>>, each bitset is a fixed-size object, so vector holds them contiguously? Actually bitset is a class with fixed size; vector will store them as an array of bitset objects, so contiguous memory. So that's fine. So total memory < 100 MB.
Now we need to be careful with indexing: creatures are numbered starting from 1 to k initially, and each new creature gets the smallest unused integer, which is sequential. So we can simply maintain a vector< bitset<4096> > creatures; initially push back dummy for index 0 to make 1-indexed? Or we can push back the k initial ones, then for each creation, compute new bitset and push back; then refer to indices by their position in the vector (since they are assigned sequentially). Queries refer to existing creatures; they are valid. So we can use 0-based vector but store creatures from index 0 as creature 1? We'll just store in a vector and when we need to access creature x, we use index x-1 if we store sequentially. Since numbers are assigned sequentially, we can keep a counter and push back each new creature. So easy.
Now the only remaining question: Do we need to consider that the original creatures themselves might be used as parents in later spells? Yes, they are valid. So we need to store their bitsets.
Implementation details:
-
Read n, k, q.
-
Read the initial matrix: We'll store a as vector< vector > a(k, vector(n)). For i=0..k-1, read n numbers.
-
Precompute bitset for each original creature (1..k). For each i from 0 to k-1:
- bitset b; (M = 1<<k? Actually M=4096, but we only need to set bits for masks where the i-th bit is set. We'll iterate mask from 0 to (1<<k)-1 and set b[mask] = ((mask>>i)&1). This is O(k * 2^k) = up to 12*4096=49152, trivial.
-
Alternatively, we can construct these bitsets using a formula: For variable i, the truth table is: for all masks, bit is 1 if mask has bit i. We can do: for mask=0; mask < (1<<k); mask++) if(mask & (1<<i)) b.set(mask). This is fine.
-
Initialize vector<bitset> creatures; for i in 0..k-1, push back b_i.
-
Then process q queries: For each query, read t, x, y. if t == 1: bitset nb = creatures[x-1] | creatures[y-1]; creatures.push_back(nb); else if t == 2: bitset nb = creatures[x-1] & creatures[y-1]; creatures.push_back(nb); else: // t == 3 // x is creature number, y is characteristic index (1-based) int cr = x-1; // index in creatures vector int char_idx = y-1; // 0-based // Build vector of pairs: (value, idx) for i=0..k-1: value = a[i][char_idx]; idx = i vector<pair<int,int>> vals(k); for i=0..k-1: vals[i] = {a[i][char_idx], i}; // sort descending by value sort(vals.begin(), vals.end(), [](auto &p1, auto &p2) { return p1.first > p2.first; }); int mask = 0; int answer = 0; // will be set when true for (auto &p : vals) { mask |= (1 << p.second); if (creatures[cr].test(mask)) { answer = p.first; break; } } cout << answer << '\n';
Edge Cases:
-
It's possible that g(mask) never becomes true? But by construction, for the full mask (all indices), g(full) must be true? Let's check. For any function derived from variables via AND/OR, is it guaranteed that g(all ones) = 1? For initial variable, g_i(all) = 1 because i is in the set. For AND of two functions: if both are 1 at all ones, then AND is 1. For OR: if either is 1, then OR is 1. So by induction, all functions we create have g(all)=1. So eventually at the full mask we will have true. So answer will be set.
-
If there are duplicate values, our algorithm returns the correct maximum t.
-
Ensure mask fits within 1<<k. Since k ≤12, mask up to (1<<k)-1.
-
We use bitset<4096>. But if k is less than 12, we still set bits for masks up to (1<<k)-1; masks above that are never used. The bitset operations on higher bits (unused) will combine zeros, which is fine.
-
For performance, we might want to precompute the sorted order and masks for each characteristic to avoid sorting per query. But it's not necessary. However, sorting 12 items 1e5 times is fine; but we can also precompute. Let's think: n up to 1e5, q up to 1e5; worst-case each query could be on a different characteristic. Sorting each time is O(k log k) ~ 12*log12 ~ 43 comparisons; that's trivial.
-
Memory for a: k*n ints; we can store as vector<vector>. But we might also store transposed to make per-characteristic access more cache-friendly? We'll be accessing all k values for a given y many times. Storing as k rows: a[i][j]. Access pattern: for a query on characteristic y, we need a[0][y], a[1][y], ... a[k-1][y]. That's reading from k different rows at the same column. That may cause cache misses because each row is contiguous but columns are spread. However, k is small (≤12), so we are reading 12 integers from different rows; the total memory for the matrix is ~1.2M ints; likely all in cache. It's fine.
Alternatively, we could store transposed: n rows of k ints. Then for a characteristic y, we can directly access an array of k ints contiguous. That may be more cache-friendly. But it's not necessary.
- For bitset, we need to specify size at compile time. Since k max 12, 1<<12 = 4096. We'll define const int KMAX = 12; const int M = 1<<KMAX; bitset might be okay. But if k is less, we still use size 4096; but that's fine.
But wait: The truth table should have size exactly 2^k, not 4096 if k<12. Because the masks we generate are only up to (1<<k)-1. For k=5, masks go from 0..31. Bits beyond 31 are unused. However, when we do bitwise OR/AND on bitsets of size 4096, we are also combining bits for masks 32..4095, which are always 0 if we initialized correctly. So it's fine. But we must be careful when we set bits for initial variable: we only set bits for masks < (1<<k). That's what we do if we iterate mask from 0 to (1<<k)-1. So bits beyond that remain 0. For derived functions, they only involve those bits; the higher bits will remain 0 because we never set them. So fine.
Now, confirm with examples.
Example 1: n=2, k=2, q=4 initial: creature1: [1,2], creature2: [2,1] We compute bitsets for k=2 (size 4). For creature1 (i=0): masks where bit0 set: 01 (1), 11 (3) -> set bits 1 and 3. Creature2 (i=1): masks where bit1 set: 10 (2), 11 (3) -> set bits 2 and 3. Type1: Sasha uses creature1 and creature2 (max). OR: bitset = (1,3)|(2,3) = bits {1,2,3} set. So creature3 bitset has bits: 1,2,3. Type2: Nikita uses creature1 and creature2 (min). AND: (1,3)&(2,3) = bit {3} set. So creature4 bitset has only bit3.
Now query 3: creature3, char1 (y=1). Column values: a[0][0]=1, a[1][0]=2. Pairs: (2, idx1), (1, idx0). Sorted: (2,1), (1,0). mask start 0.
- after first: mask = 1<<1 = 2 (binary10). test creature3[2]? creature3 has bits at 1,2,3. mask=2 (bit2) => true? Since bit2 set (mask=2 corresponds to binary 10, which is 2 decimal). Yes true, answer=2. Output 2. matches.
Second query 3: creature4, char2 (y=2). Column: a[0][1]=2, a[1][1]=1. Pairs: (2, idx0), (1, idx1). Sorted: (2,0) then (1,1). mask after first: mask=1<<0=1. test creature4[1]? creature4 only has bit3. mask=1 false. after second: mask=1| (1<<1)=3. test creature4[3] true, answer=1. Output 1. matches.
Example 2: Let's test quickly mentally but seems correct.
Thus solution appears sound.
Now, we must ensure that the Boolean function derived from OR/AND exactly corresponds to the threshold condition of the original max/min expression. Let's prove: For any expression built from variables using max and min, define f(v). For any threshold t, define g_t(mask) = 1 if f(v) >= t, else 0, where mask encodes which v_i >= t. We claim that g_t(mask) = h(mask) where h is the Boolean expression obtained by replacing max with OR and min with AND. Proof by structural induction: For leaf i: f(v)=v_i. Then f(v)>=t iff v_i>=t, i.e., mask_i=1, so h(mask)=mask_i. For internal node with children f1,f2: if operation is max, then f(v)=max(f1(v),f2(v)). Then f(v)>=t iff f1(v)>=t OR f2(v)>=t. By induction, that equals h1(mask) OR h2(mask). Similarly for min: f(v)>=t iff f1(v)>=t AND f2(v)>=t -> h1(mask) AND h2(mask). So h(mask) does not depend on t; it's the same Boolean function for all t. So we can store h.
Thus approach is correct.
Potential pitfalls: When we compute f(v) as the maximum t such that h( {i|v_i>=t} )=1, we need to consider that t may not be exactly one of the v_i values. But since h is monotone and values are from v_i, the maximum t is always attained at some v_i (since if we pick any t between two distinct v_i values, the set {i|v_i>=t} is the same as for the next higher v_i). So it's enough to check at the distinct values.
Implementation details: We'll need to handle large n and q efficiently.
Now, let's consider if there is any nuance with the fact that creatures are numbered starting from 1 and new creatures get smallest unused number. Since we push sequentially, it matches.
Edge Cases: k=1. Then there is only one original creature. The truth table size is 2^1=2. The initial creature's bitset: for i=0, masks: mask=0 (bit 0?), we set bits where bit0=1: mask=1 only. So B[1] has bit1 set? Actually masks: 0 and 1. We set for variable: bit set for mask 1. For k=1, (1<<k) =2. Good. Now operations: max and min on same or other creatures? There could be other creatures created. Since there is only one original, any derived creature's function will still be just the variable (since OR/AND of variable with itself yields itself). But that's fine. For query, we sort the single value; mask after adding only index0; test; answer should be that value. So works.
Now, check memory: storing bitset<4096> for each creature, 100k creatures -> 51.2 MB. In C++, using std::bitset<4096> as an object, vector stores them contiguously; each bitset object is exactly 512 bytes? According to standard, std::bitset stores an array of (N / bits per word) words. For N=4096, likely it stores 4096/8=512 bytes? Actually bitset stores bits packed; typical implementation uses an array of unsigned long; size is (N+CHAR_BIT-1)/CHAR_BIT bytes? Actually bitset stores bits, so size in bytes is at least N/8. For 4096 bits, that's 512 bytes. Possibly plus some alignment. So around 512 bytes. 100k * 512 = 51.2 MB. That's okay.
But in many contest environments, memory limit may be 256 MB or 512 MB. This is fine.
Alternatively, to reduce memory, we could use a more compact representation using 64-bit words only when k is small? But not necessary.
Now, we should also consider the time to construct initial bitsets: we could precompute all initial bitsets using a faster method: For each i from 0 to k-1, we can set bitset by iterating mask and setting if mask&(1<<i). That's O(k*2^k) = about 50k operations, trivial.
But note: The matrix a may be large; reading it as ints is okay.
One more nuance: The problem states that characteristics are n up to 1e5, and queries up to 1e5. In our solution, for each type3 query, we loop over k (<=12) and for each we test the bitset. That is fine.
Now, think about potential pitfalls with bitset indexing: In bitset, operator[] returns a reference to a bit (or a proxy). The test method is safer. We'll use .test(idx). That performs bounds checking in debug maybe? In typical competitive programming, using operator[] is fine and faster. We'll use [] if we ensure index < size.
But we need to be careful: mask may be up to (1<<k)-1 which is at most 4095, within bounds.
Now, let's test more cases:
Case: k=3, values: a1=3, a2=2, a3=1. Suppose we have creature = min(creature1, creature2) (Nikita). Its Boolean function h = x1 & x2. For column with values (3,2,1). Compute f = min(3,2)=2. Let's see algorithm: sorted: (3,idx0), (2,idx1), (1,idx2). mask after idx0: mask=1<<0=1; h(1) = x1 & x2? Actually h(1) = (bit0=1, bit1=0, bit2=0) => false. after idx1: mask=1|2=3 (bits 0 and 1). h(3) = (1&1) = true, so answer = 2. correct.
Case: creature = max(min(1,2),3) (i.e., max(min(x1,x2), x3) ). Boolean h = (x1 & x2) | x3. Column: (3,2,1). Sorted: (3,idx0), (2,idx1), (1,idx2). mask after idx0: mask=1; h(1) = (0|0?) Actually x3? Wait ordering: we need to map indices: idx0 is creature1? Actually we need to keep consistent: indices correspond to original creatures. Suppose idx0 = creature1, idx1 = creature2, idx2 = creature3. Then after first (value 3 from creature1): mask=1<<0=1. h(1): (x1=1, x2=0, x3=0) => (1&0)|0 = 0 -> false. After second (value 2 from creature2): mask=3 (bits0 and1). h(3): (1&1)|0 = 1 -> true, answer=2. But is f(v) = max(min(3,2),1) = max(2,1)=2. correct.
If column values: (1,2,3). Sorted: (3,idx2), (2,idx1), (1,idx0). after idx2: mask=4 (binary100). h(4): (x1=0,x2=0,x3=1) => (0&0)|1 = 1 -> true, answer=3. f = max(min(1,2),3) = max(1,3)=3. correct.
So works.
Now, what about functions like max(x1, x2) & x3? But that's not directly a combination because we only have binary operations, but we can create a tree: first compute max(x1,x2) then min with x3? That's min(max(x1,x2), x3) which is different. Actually to get (x1 OR x2) AND x3, we would need to compute AND of max and another? That's min of the two: min( max(x1,x2), x3). So any expression is a tree of max/min; the Boolean function is the corresponding combination of OR/AND. So it's exactly what we have.
Thus, solution stands.
Now, we need to implement efficiently.
Potential improvements:
- Since we will be doing many bitset OR/AND operations, using std::bitset's operators is fine.
- We'll use a vector<bitset> creatures; initially reserve k+q+5 to avoid reallocation.
Implementation steps:
- #include <bits/stdc++.h>
- using namespace std;
- const int KMAX = 12; // max k
- const int M = 1 << KMAX; // 4096
- using Bits = bitset; // but M is 4096.
But bitset size must be compile-time constant. M = 4096 is fine.
- int main() { int n, k, q; cin >> n >> k >> q; vector<vector> a(k, vector(n)); for (int i = 0; i < k; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } vector creatures; creatures.reserve(k + q); // approx // create initial bitsets for (int i = 0; i < k; i++) { Bits b; for (int mask = 0; mask < (1 << k); mask++) { if (mask & (1 << i)) { b.set(mask); } } creatures.push_back(b); } // process queries for (int i = 0; i < q; i++) { int t, x, y; cin >> t >> x >> y; if (t == 1) { Bits nb = creatures[x-1] | creatures[y-1]; creatures.push_back(nb); } else if (t == 2) { Bits nb = creatures[x-1] & creatures[y-1]; creatures.push_back(nb); } else { // t == 3 int cr = x-1; int col = y-1; // build vector of pairs vector<pair<int,int>> vals(k); for (int idx = 0; idx < k; idx++) { vals[idx] = {a[idx][col], idx}; } sort(vals.begin(), vals.end(), greater<pair<int,int>>()); // sorts by first then second descending // Actually greater<pair<int,int>> compares by first then second. Since we only care about value, it's fine. int mask = 0; int ans = 0; for (auto &p : vals) { mask |= (1 << p.second); if (creatures[cr][mask]) { // using operator[] for bit access; returns a proxy (but we can use test if preferred) ans = p.first; break; } } cout << ans << '\n'; } } return 0; }
But note: Using greater<pair<int,int>> sorts by first descending, then second descending. That's fine. We don't care about order of indices for equal values.
Potential performance issue: In the loop for creating initial bitsets, we iterate mask from 0 to (1<<k)-1 for each i. That's O(k * 2^k) = up to 12*4096 = 49152, fine.
But we might also compute these bitsets via precomputation for all variables at once? Not necessary.
Now, we must ensure that we use mask up to (1<<k)-1. However, we defined M = 1<<12 = 4096. So if k < 12, (1<<k)-1 < M, but we still loop mask up to (1<<k)-1. That's correct. The bits beyond remain 0.
Now, check for correctness when k=0? Not possible, k>=1.
Now, verify with sample.
Let's run through sample 2 quickly:
Input: 5 3 8 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 1 1 2 1 2 3 2 4 5 3 6 1 3 6 2 3 6 3 3 6 4 3 6 5
First, n=5, k=3, q=8. Initial creatures: C1: [1,2,3,4,5] C2: [5,1,2,3,4] C3: [4,5,1,2,3]
We'll compute bitsets for k=3. M=8. For i=0 (C1): set mask bits where bit0 set: masks 1,3,5,7? Actually all odd numbers: 1,3,5,7. For i=1 (C2): bit1 set: masks with second bit: 2,3,6,7. For i=2 (C3): bit2 set: masks 4,5,6,7.
Now queries:
-
t=1 x=1 y=2: Sasha uses C1 and C2 -> OR of bitsets C1|C2 = bits where either bit0 or bit1 set: masks: {1,2,3,5,6,7? Let's compute: C1 has {1,3,5,7}; C2 has {2,3,6,7}; union = {1,2,3,5,6,7}. So creature4 (since numbers: 1,2,3 are initial; next is 4) gets this bitset.
-
t=1 x=2 y=3: Sasha uses C2 and C3 -> OR: C2|C3 = {2,3,4,5,6,7}? C2: {2,3,6,7}; C3:{4,5,6,7}; union = {2,3,4,5,6,7}. Creature5.
-
t=2 x=4 y=5: Nikita uses creature4 and creature5 (min) -> AND of their bitsets: C4 = {1,2,3,5,6,7} C5 = {2,3,4,5,6,7} Intersection = {2,3,5,6,7}? Actually common: 2,3,5,6,7. Also maybe? 1 is only in C4, 4 only in C5. So intersection = {2,3,5,6,7}. Creature6.
Now queries 4-8: ask creature6, characteristics 1..5.
We need to compute f6 for each column.
Let's compute manually:
Column 1: values: C1=1, C2=5, C3=4. Sorted: (5,idx1), (4,idx2), (1,idx0). We'll compute h6 mask.
h6 is the Boolean function for creature6: ( (x1 OR x2) AND (x2 OR x3) )? Actually from operations: C4 = C1 OR C2; C5 = C2 OR C3; C6 = C4 AND C5. So h6 = (x1 ∨ x2) ∧ (x2 ∨ x3). That simplifies? Let's keep as is.
Now for column1: mask after first (value 5, idx1): mask includes idx1 only (bit1). h6( mask=010 ) =? (x1=0,x2=1,x3=0) => (0∨1)=1, (1∨0)=1, ∧ => 1. So true, answer=5. Output 5. matches sample first output 5.
Column2: values: C1=2, C2=1, C3=5. Sorted: (5,idx2), (2,idx0), (1,idx1). mask after idx2: mask=100 (4). h6(4): (x1=0,x2=0,x3=1) => (0∨0)=0, (0∨1)=1, ∧ => 0 => false. after idx0: mask=100|001=101 (5). h6(5): (x1=1,x2=0,x3=1) => (1∨0)=1, (0∨1)=1, ∧ =>1 => true, answer=2. Output 2. matches sample second output 2.
Column3: values: C1=3, C2=2, C3=1. Sorted: (3,idx0), (2,idx1), (1,idx2). mask after idx0: 001 -> h6(1): (1∨0)=1, (0∨0)=0 => 0 false. after idx1: 011 (3): h6(3): (1∨1)=1, (1∨0)=1 => 1 true, answer=2? Wait current value is 2 (from idx1). But sample output for column3 is 2. Indeed output 2. Good.
Column4: values: C1=4, C2=3, C3=2. Sorted: (4,idx0), (3,idx1), (2,idx2). mask after idx0: 001 -> h6(1): false (as above). after idx1: 011 -> h6(3): true, answer=3. Sample output 3. Good.
Column5: values: C1=5, C2=4, C3=3. Sorted: (5,idx0), (4,idx1), (3,idx2). mask after idx0: 001 -> h6(1) false. after idx1: 011 -> h6(3) true, answer=4. Sample output 4. Good.
All match.
Thus solution works.
Now, we must also handle potential overflow? Not.
Now, consider time to create initial bitsets: we loop over mask up to (1<<k). But we can also create using pattern: For variable i, the bitset is such that all masks with ith bit set are 1. We could compute by: for (int mask = 0; mask < (1<<k); mask++) if (mask>>i &1) b.set(mask); okay.
But we might also compute using a precomputed array of size (1<<k) for each i. But okay.
Now, note: For k=12, (1<<k)=4096, that's small. So fine.
Now, ensure that we use correct indexing for bits: Our mask bits correspond to original creature indices 0..k-1. When we set mask |= (1 << idx), idx is from 0 to k-1, so mask is correct.
Now, for type1/2 queries, we refer to creatures by their numbers (x and y). Those numbers are guaranteed to exist. Since we push back sequentially, the index is number-1.
Now, about reading input: Use scanf for speed because 1e5 lines and many numbers. But cin with ios_base::sync_with_stdio(false) is probably okay. However, reading the matrix: k*n up to 1.2e6 numbers, plus q up to 1e5 lines with three ints each. So total ~1.3M numbers; cin is fine.
But we may need to be careful with endl; use '\n'.
Now, memory: vector<bitset> of size up to 1e5+12. Each bitset is 512 bytes, so ~51MB. Plus matrix a: k * n ints = up to 12*1e5=1.2e6 ints = ~4.8MB. Plus other overhead. So total < 70MB. Acceptable.
Now, we need to confirm that the bitset operations are not too heavy. For each type1/2, we do bitset OR/AND, which loops over 64 words (if implemented). That is trivial.
Potential issue: When k is small, we still use bitset<4096> which might be larger than needed but that's okay.
Now, we might also consider alternative approach using bitmask representation of minimal true subsets (antichain). But bitset truth table is simpler.
Thus, solution is solid.
Now, let's think if there is any hidden complication: The problem states that n ≤ 1e5, k ≤ 12. So our approach is valid.
One more nuance: The new creature gets the smallest unused number. Since we process queries sequentially and push back in order, the next number is always size+1. So that matches.
Now, ensure that when we process query type3, the creature x is already created; we have its bitset in the vector. Good.
Edge Cases:
- If there is a type3 query immediately after creation? That's fine.
- If there are many creations, the vector grows.
Now, test with random small cases to ensure correctness. We can do mental testing.
We should also consider if we need to handle that the function for original creature i is exactly the variable, which we set. For k=12, we have 12 initial functions. Good.
Now, is there any scenario where the Boolean function we compute via OR/AND is not exactly the threshold function for the numeric max/min? We already argued by induction.
Thus, solution is correct.
Now, we should produce final answer.
But before finalizing, we might consider if we can further reduce memory by storing bitsets only for nodes needed? But we need all for future references, so we must store them.
One more thought: Since k is small, we could compute the answer for type3 query without using bitset by evaluating the expression tree for that column on the fly using memoization. That would be O(size of tree) per query, which could be too much. So bitset method is better.
Now, ensure that we used bitset<4096>. But 4096 is 2^12, but if k=12, (1<<12) = 4096, so indices 0..4095 inclusive, that's 4096 bits. bitset<4096> has bits 0..4095. So mask values up to 4095, okay.
Now, we need to be careful about shift: (1 << idx) with idx up to 11 fits in int.
Now, implementation details:
- We'll define constexpr int MAXM = 1 << 12; // 4096
- using Bits = bitset;
But we need to know k to know up to which mask to set for initial bitsets. We'll use (1<<k) for loops.
Potential improvement: Instead of building bitsets for initial creatures via loop over all masks, we could use a formula: For each i, we can set bitset by generating masks with ith bit set. But that's basically the same.
Alternatively, we could precompute a table for all masks once: For each mask, store which bits are set. Not needed.
Now, one more thing: In query type3, we sort vals. If we want to avoid sorting each time, we could precompute for each column the sorted order and the cumulative masks. For each column j, we can pre-sort the indices by value descending, and also precompute an array of masks: prefix_mask[r] = mask of first r indices (in sorted order). Then per query we just need to iterate r from 1..k and test. However, we still need to break at first true, but we also need the value at that r. So we need the value for each r. So we could store for each column a vector of pairs (value, mask_after_adding) in sorted order. Precomputing this would take O(n * k log k) which is fine, and then per query O(k) with less overhead of sorting. But sorting per query is also fine; but to be safe, we can implement per query sorting, as k is very small. I'll keep per query sorting.
But note: For each query we allocate a vector of size k (12) on stack; that's fine.
Potential micro-optimizations: Use array<pair<int,int>, KMAX> instead of vector. But okay.
Now, double-check if there is any off-by-one: The characteristic index y is from 1 to n, we use col = y-1.
Now, confirm that the answer for type3 is always found (since eventually mask = (1<<k)-1 gives true). So we don't need to handle case where answer remains 0.
Now, edge case: When k=0? Not possible.
Now, we should also consider that the input numbers aij can be up to 1e9, so we use int (32-bit may be enough up to 1e9, but 1e9 fits in 32-bit signed? 1e9 < 2^31-1, so int is fine. But sum or product not needed.
Now, potential pitfalls with bitset indexing: bitset's operator[] returns a reference to a bit (like a proxy) but it's fine. Alternatively, use test() which does bounds check in debug; but in competitive programming we often use operator[] for speed. However, operator[] for bitset returns a bitset::reference, which is okay. I'll use test to be safe and clearer; it's still O(1). But test might have a small overhead; but with 12 tests per query, it's negligible.
Now, we should also consider the fact that when we do creatures[cr].test(mask), mask is up to 4095. test expects an index; it's okay.
Now, one more nuance: The bitset size is 4096, but we may have masks up to 4095, so the highest bit index is 4095. In C++ bitset, the indexing is from 0 to N-1. So fine.
Now, finalize solution.
But wait, we need to ensure that for initial creatures, the bitset correctly represents the Boolean function for threshold. However, for leaf i, we set bit for mask m if (mask & (1<<i)) is true. That is correct.
Now, what about the possibility that the Boolean function for a creature could be constant 1? Could that arise? For example, if we OR all variables, the function is OR over all xi. That yields 1 only when at least one variable is true; not constant 1. Actually OR over all variables is true when any xi is true; but for the empty mask (all false), it's false. So it's not constant 1. Could we ever get constant 1? If we AND something? No, AND of variables yields true only when all variables true. So constant 1 would require that for empty mask it's true, but that cannot happen because from leaves that are false on empty mask, and AND/OR preserve false on all-zero? Actually if we have an expression that always evaluates to true regardless of inputs, is that possible using only variables, AND, OR? No, because if all inputs are false (0), any expression built from variables (which are false) and AND/OR will be false. So constant true is impossible. So our bitset will have at least bit 0 (mask 0) = 0. Good.
Now, we need to ensure that for mask representing the set of indices with value >= t, we treat t as a numeric threshold. But what if there are values that are not exactly one of the a[i][j]? For example, if we have values 5 and 3, and we consider t=4. The set {i | v_i >=4} is only the index with 5. That set is also captured by t=5 (since for t=5, set is same? Actually for t=5, set is {5} if exactly 5; for t=4, set is {5} as well because 5>=4. So the set for t=4 is same as for t=5 (if no value between). So the maximum t that yields true will be the maximum value among v_i for which the condition holds. So checking only at the distinct v_i suffices.
Thus, algorithm correct.
Now, final implementation.
Potential improvement: Since we only need to test g(mask) for masks that are prefixes of the sorted order, we could precompute for each column the sorted list of indices and the corresponding masks and values. But not needed.
Now, test with k=12, n=1, q=1e5 all type3 queries. Our per query sorting of 12 items is fine.
Now, I'll write the code accordingly.
But wait: There is a detail: The matrix a is given as k lines each with n numbers. In our code we stored as a[k][n]. However, when we access a[idx][col], idx is from 0..k-1, col from 0..n-1. That's fine.
Now, one more nuance: The number of creatures can be up to k + (#type1/2). But if many queries are type3, the vector creatures may not grow much. So memory less.
Now, ensure we use .reserve to avoid reallocation.
Now, finalize.
But before final answer, let's consider if there is any alternative simpler representation: maybe using bitmask of size k for each creature to represent which original creatures' values can be the outcome? Not sufficient because function may be more complex.
Thus, we proceed.
Now, I'll produce final solution explanation and code.
Implementation plan:
- Read n, k, q.
- Read initial characteristics into a 2D vector a of size k x n.
- Define constant MAXM = 1 << 12 (4096).
- Define Bits = bitset.
- Create vector creatures; reserve(k+q+5).
- For i in 0..k-1: create Bits b; loop mask from 0 to (1<<k)-1: if (mask >> i) & 1, set b[mask]=1; push b.
- Process q queries:
- read t, x, y.
- if t == 1: creatures.push_back(creatures[x-1] | creatures[y-1]);
- else if t == 2: creatures.push_back(creatures[x-1] & creatures[y-1]);
- else: int cr = x-1, col = y-1; vector<pair<int,int>> vals(k); for i=0..k-1: vals[i] = {a[i][col], i}; sort(vals.begin(), vals.end(), [](auto &p1, auto &p2) { return p1.first > p2.first; }); int mask = 0, ans = 0; for (auto &p : vals) { mask |= (1 << p.second); if (creatures[cr].test(mask)) { ans = p.first; break; } } cout << ans << '\n';
Edge Cases: None.
Now, confirm with sample.
Let's code.
But note: The bitset size is 4096, but if k is less than 12, the truth table still uses only the lower 2^k bits. However, when we do bitwise OR/AND on the whole bitset, the bits beyond 2^k will be zero, so no problem. However, when we test mask, mask is always less than 2^k, so we only test those bits. So fine.
Potential problem: For k < 12, the initial bitset may have some bits set beyond 2^k if we loop up to MAXM-1? But we loop only up to (1<<k)-1, so bits beyond are 0. So safe.
Now, we also need to consider that the bitset index mask is an integer, but when k<12, mask could be e.g., for k=5, mask up to 31. Bits beyond 31 are not set, but they may be accidentally tested? No, we only test masks up to 31.
Thus, okay.
Now, finalize.
I think this is the intended solution given constraints.
Let's produce final answer with explanation.
But before final, think about any possible overflow: (1 << idx) with idx up to 11, safe.
Now, check memory again: vector<bitset<4096>> for 100k elements: each bitset object may be 512 bytes, but also the vector overhead stores pointers to each? Actually vector stores objects directly, not pointers, so it's contiguous array of bitset objects. Each bitset object is exactly its data (likely 512 bytes). So total memory is N * sizeof(bitset<4096>). What is sizeof(bitset<4096>)? In GCC, it's typically 512 bytes (since it stores as an array of unsigned long). I can check: For N=4096 bits, it's 512 bytes. So 100k*512 = 51.2 MB. Good.
Now, might there be a problem with time due to bitset operations being heavy? 64-bit operations per creation, 100k creations -> 6.4M 64-bit operations, trivial.
Now, potential issue: When we sort vals, we use greater<pair<int,int>>. But we must include etc. Not a problem.
Now, final code.
I'll provide final answer with explanation.
Now, produce final output. ```cpp
#include <bits/stdc++.h> using namespace std;
constexpr int MAX_K = 12; constexpr int MAX_MASK = 1 << MAX_K; // 4096 using Bits = bitset<MAX_MASK>;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k, q; cin >> n >> k >> q; // original creatures' characteristics vector<vector<int>> a(k, vector<int>(n)); for (int i = 0; i < k; ++i) for (int j = 0; j < n; ++j) cin >> a[i][j]; // store the Boolean function of each creature as a truth table vector<Bits> creatures; creatures.reserve(k + q); // initial creatures: projection on one variable for (int i = 0; i < k; ++i) { Bits b; for (int mask = 0; mask < (1 << k); ++mask) if (mask & (1 << i)) b.set(mask); creatures.push_back(b); } while (q--) { int t, x, y; cin >> t >> x >> y; --x; // to 0‑based index in creatures vector if (t == 1) { // Sasha: max → OR Bits nb = creatures[x] | creatures[y-1]; creatures.push_back(nb); } else if (t == 2) { // Nikita: min → AND Bits nb = creatures[x] & creatures[y-1]; creatures.push_back(nb); } else { // query: characteristic y of creature x int cr = x; int col = y - 1; // characteristic index 0‑based // collect values of the original creatures for this column vector<pair<int, int>> vals(k); for (int i = 0; i < k; ++i) vals[i] = {a[i][col], i}; // sort descending by value sort(vals.begin(), vals.end(), [](const auto &p, const auto &q) { return p.first > q.first; }); int mask = 0; int ans = 0; for (const auto &p : vals) { mask |= 1 << p.second; if (creatures[cr].test(mask)) { ans = p.first; break; } } cout << ans << '\n'; } } return 0;}