Background

Year after year, under the eaves with flower patterns, we boil snow with tangli,
From childhood to some day when you and I drift to the ends of the sky.
The sky is pale, the sky is blue; the night rain wets my clothes,
Once a year, the letters arrive, yet there are only a few words.

— Yinlin, “Tangli Jianxue”.

Problem Description

While Fusu was listening to “Tangli Jianxue”,

uoj.ac/problem/425): “I’ve solved this CTT problem, you trash Fusu, come and do it.” Fusu took a closer look—wasn’t this an s* problem? He coded and submitted it, only to find he had misread the statement. But the finished code could not be wasted, so this problem was created.

The protagonist in the lyrics and her friend write letters to each other once a year, for a total of $m$ years. To simplify the problem, we assume that the content of each letter is a binary code, and all binary codes have length $n$. That is, each letter is a string of length $n$ containing only characters 0 or 1.

One day she took out all the letters her friend wrote to her. The letter written in year $i$ is numbered $i$. Because the letters have been kept for too long, some characters have become blurred. We mark such positions as ?. A ? character can be interpreted as 0 or 1. Since her friend is also a human and thus follows human nature, the content written during a continuous period of time may be the same. Now she wants to ask you: for all letters in a continuous year interval $[l,r]$, assuming her friend showed “human nature” in this period and wrote the same sentence, how many possible sentences can that sentence be? In other words, how many strings $S$ are there such that every letter in this interval could have content $S$?

A string $A$ of length $n$ containing only 0,1,? could be a string $B$ if and only if $B$ satisfies:

• The length of $B$ is also $n$.
• $B$ contains only characters 0,1.
• Every position that is 0 in $A$ is also 0 in $B$.
• Every position that is 1 in $A$ is also 1 in $B$.
• Every position that is ? in $A$ can be 0 or 1 in $B$.

She may also suddenly realize that she misread the content of some year’s letter, so she may modify the content of a certain year’s letter into another length-$n$ string containing only 0,1,?.

Input Format

Each input file contains exactly one test case.

The first line contains three integers separated by spaces, representing the string length $n$, the number of strings $m$, and the number of operations $q$.

The next $m$ lines each contain a string of length $n$. The string $s_i$ on line $(i + 1)$ represents the content of the letter in year $i$.

The next $q$ lines describe operations. The first number of each line is the operation code $opt$.

• If $opt=0$, it is followed by two integers $[l,~r]$, representing a query operation.
• If $opt=1$, it is followed by an integer $pos$, then after a space a string $t$ of length $n$, representing modifying the $pos$-th string to the new string $t$.

Output Format

To avoid an excessively large output, output one line with one number: the XOR of the answers of all queries, and then XOR it with $0$.

3 3 5
010
0?0
1?0
0 1 2
0 2 3
1 3 0??
0 2 3
0 1 3

2

Hint

Sample 1 Explanation

• For the first query, only the string 010 satisfies the requirement.
• For the second query, since the first bit of the second string is 0 and the first bit of the third string is 1, no string satisfies the requirement.
• After the modification, the third string becomes 0??.
• For the fourth query, there are two valid strings: 000 and 010.
• For the fifth query, only 010 is valid.

Therefore the answers are $1,0,2,1$. Their XOR, and then XOR with $0$, equals $2$.

---

Constraints

This problem uses bundled subtasks, with a total of 7 subtasks.

Subtask ID	$m =$	$q =$	$n =$	Subtask Score
$1$		$0$	$1$	$5$
$2$	$102$		$10$	$10$
$3$	$1003$			$15$
$4$	$1004$	$10004$	$30$
$5$	$100005$	$500005$	$1$
$6$	$100006$	$50006$	$30$	$10$
$7$	$100007$	$1000007$		$30$

For all testdata, it is guaranteed that:

• $1 \leq m \leq 10^5 + 7$, $0 \leq q \leq 10^6 + 7$, $1 \leq n \leq 30$.
• $0 \leq opt \leq 1$, $1 \leq pos \leq m$, $1 \leq l \leq r \leq m$.
• The lengths of $s_i$ and $t$ are both $n$, and they contain only 0,1,?.
• The total length of input strings does not exceed $5 \times 10^6$. The data is generated under Linux, so line breaks do not include \r.

---

Hint

• Please pay attention to the impact of constant factors on program efficiency.
• Please pay attention to the impact of input reading on program efficiency.
• Please note that the question mark in the input is the English question mark, whose ASCII value is $63$.

Note: To reduce the acceptance rate of incorrect solutions, the time limit was changed from 2000 ms to 1500 ms in July 2020.

Translated by ChatGPT 5