PROGRAMMING:Hard disk repair
###Title Description
One day, the school's server failure, resulting in damage to the hard disk. Because the hard disk stores the students' scores, so the teachers hope you can help restore the data in the hard disk. Because the fault happened very suddenly, the teacher confused the order of the hard disk in panic
This batch of hard disk adopts independent hard disk redundant array (RAID), a modern common storage technology. In a certain form, it stores data in multiple hard disks in a decentralized and redundant manner, so that when some disks are unavailable, the integrity of data can still be guaranteed. Raid is divided into many levels, providing a wealth of redundancy and performance options. This batch of hard disks involves a common level RAID5.
###Topic background
####Raid Fundamentals
Raid can provide the redundancy of a hard disk, that is, at most one hard disk in the array is allowed to fail without losing data. The basic principle of RAID5 is exclusive or operation ($$\ oplus $$), existing number $$a_{ 1}, a_{ 2}, \ldots, a_{ n}$$
Let $$p = a_{ 1} \oplus a_{ 2} \oplus \cdots \oplus a_{ n}=\bigoplus_{ i=1}^{n} a_{ i} $$
Available $$a_{ k}=p \oplus \bigoplus_{ i=1 . . n,i \neq k} a_{ i}$$
The above formula means that in $$p $$and $$a_{ 1} \ldots a_{ n} In the number of $$(n + 1) $, the rest can be inferred from any $$n $. This is the basic principle of RAID5.
Therefore, a simple storage scheme of $$(n + 1) $$block disk is to store the data in blocks in the first $$n $$block disk, and then store the XOR result of the data in the corresponding position on the first $$n $$block disk in the second $$(n + 1) $$block disk. This scheme can achieve the redundancy of $$1 $$hard disk. However, it is obvious that if all the hard disks do not fail, when reading data, the last disk will not be used at all, which is a waste of performance. Therefore, the current RAID5 storage method adopts the strip $$, which distributes the stored data evenly on all disks, thus improving the read-write performance.
####Hard disk and its organization
Modern hard disk can be regarded as a kind of persistent storage device which can read and write randomly by block. Most hard disks have a block size of $$512 $$bytes or $$4096 $$bytes. All blocks on the hard disk are numbered consecutively starting from $$0 $. Every time the hard disk is read or written, it should be in blocks. When reading or writing, the number of the block to be read or written is passed in, and the whole block is read or written one at a time.
RAID device can organize multiple hard disks into a certain storage structure. In the upper software, the organized storage structure looks like a whole hard disk. Therefore, the number of the block in the read-write instruction sent by the upper software to the raid should be replaced by the RAID device appropriately, and reflected in the operation of a specific hard disk or several hard disks.
####Striping and data layout
In RAID5, an important parameter is the stripe size** Stripe * * refers to continuous and equal size data blocks, which is the basic unit of RAID5 for data layout. For example, suppose that a hard disk has $$1024 $$blocks and the stripe size is $$8 $$blocks, then the hard disk is divided into a total of $$128 $$stripes, the block numbered $$[0,8) $$is on the first stripe, the block numbered $$[8,16) $$is on the second stripe, and so on. Generally, if the stripe is also numbered from 0, and the stripe size is $$s $$blocks, then the stripe number of the block with number $$B $$is $$- left / lfloor / frac {B} {s} right / rfloor $$.
For RAID5 storage with $$(n + 1) $$hard disks, we use the strip number of $$k $$on each hard disk to store the strip number of $$[kn, (K + 1) n) $(a total of $$n $). The specific storage method of the $$n $$strips is: first, according to certain rules, select a hard disk as the check disk, store the XOR sum of the $$n $$strips, and then store the $$n $$strips in other hard disks in a certain order. The rule for selecting the check disk is: with the increment of $$k $, select the check disk from the last disk in descending order until the first disk, and then start from the last disk again. The order of saving data strips is: starting from the next disk of the selected check disk, saving data strips successively until the last disk, and then starting from the first disk, saving the remaining data strips successively until the last disk of the selected check disk.
Let's take $$n = 3 $$as an example to show the strip layout.
**It is now known that the block size of these hard disks is $$4 $$bytes**
###Input format
Read in data from standard input.
The first line of input contains three positive integers, $$n $$($$n / GEQ 2 $$), $$s $$and $$l $$, representing the number of hard disks in the array, the stripe size (in blocks) of the array, and the number of existing hard disks.
The next $$l $$line contains a non negative integer separated by spaces and a string of equal length without spaces that is an integral multiple of $$8 $. This integer is the serial number of this hard disk starting from zero. The string only contains numbers * * 0 ~ 9 * * and uppercase letters * * a ~ f * *, and each two characters constitute a $$16 $$decimal number, representing one byte of hard disk content. Input hard disk set guarantee: to the hard disk has been added a number of appropriate content of the hard disk, they can just form a legal, data error free RAID5 array. Input data guarantee: the stripe size of the array can divide the size of each hard disk.
The next line contains a positive integer, $$M $, indicating the number of read operations.
The next $$M $$rows, each representing a read operation, include a non negative integer $$B_{ i} $$, which indicates the number of the block to read.
###Output format
Output to standard output.
The output contains rows of $$M $.
For each read operation, one line of output is generated. If the read operation can be carried out or calculated from the existing hard disk data, the output length of the string is $$8 $, which only contains the number * * 0 ~ 9 * * and capital letters * * a ~ f * *, and each two characters constitute a $$16 $$decimal number, indicating the content of the read data block. If the read operation cannot be performed due to one of the following conditions, a minus sign (-) is output:
-The array is incomplete, and the hard disk of the read block is missing, and the data cannot be calculated from the existing hard disk data;
-The specified block exceeds the total array length.
###Input sample 1
```in
2 1 2
0 000102030405060710111213141516172021222324252627
1 000102030405060710111213141516172021222324252627
two
0
one
```
###Output sample 1
```out
00010203
04050607
```
###Explanation of example 1
The RAID5 array is composed of two disks. The stripe size is $$1 $$block ($$4 $$bytes) long. The data of the two disks are given. Note that when RAID5 has only two disks in the array, $$p = a_{ 1} Therefore, the data in the two disks are the same, which are the contents of the RAID array. Therefore, any disk can be read.
###Input sample 2
```in
3 2 2
0 000102030405060710111213141516172021222324252627
1 A0A1A2A3A4A5A6A7B0B1B2B3B4B5B6B7C0C1C2C3C4C5C6C7
two
two
five
```
###Output sample 2
```out
A0A1A2A3
A0A0A0A0
```
###Explanation of example 2
According to the meaning of the topic, the RAID5 array is composed of three disks, the stripe size is $$2 $$block ($$8 $$bytes) long, and the data of $$0 $$and $$1 $$disks are given, and the $$2 $$disk is missing. Therefore, the layout of the whole RAID5 array is shown in the figure.
In the figure, a rectangle separated by dotted lines represents a block, and a square composed of two continuous rectangles represents a strip. When reading block No. $$2 $, the data is located in block No. $$0 $$of disk No. $$1 $, so the result is a0a1a2a3; When reading the block No. $$5 $, the data is located in the block No. $$3 $$of disk No. $$2, and the disk is missing. Therefore, it is necessary to XOR the data at the corresponding positions of the other two disks to get 14151617 $$\ oplus $$b4b5b6b7 $= $$A0.
###Data range and tips
$$2 \leq n \leq 30$$；$$ 2 \leq s \leq 100$$；$$ m \leq 30$$； The total hard disk space does not exceed $$10kib $< br>
answer：If there is no answer, please comment
One day, the school's server failure, resulting in damage to the hard disk. Because the hard disk stores the students' scores, so the teachers hope you can help restore the data in the hard disk. Because the fault happened very suddenly, the teacher confused the order of the hard disk in panic
This batch of hard disk adopts independent hard disk redundant array (RAID), a modern common storage technology. In a certain form, it stores data in multiple hard disks in a decentralized and redundant manner, so that when some disks are unavailable, the integrity of data can still be guaranteed. Raid is divided into many levels, providing a wealth of redundancy and performance options. This batch of hard disks involves a common level RAID5.
###Topic background
####Raid Fundamentals
Raid can provide the redundancy of a hard disk, that is, at most one hard disk in the array is allowed to fail without losing data. The basic principle of RAID5 is exclusive or operation ($$\ oplus $$), existing number $$a_{ 1}, a_{ 2}, \ldots, a_{ n}$$
Let $$p = a_{ 1} \oplus a_{ 2} \oplus \cdots \oplus a_{ n}=\bigoplus_{ i=1}^{n} a_{ i} $$
Available $$a_{ k}=p \oplus \bigoplus_{ i=1 . . n,i \neq k} a_{ i}$$
The above formula means that in $$p $$and $$a_{ 1} \ldots a_{ n} In the number of $$(n + 1) $, the rest can be inferred from any $$n $. This is the basic principle of RAID5.
Therefore, a simple storage scheme of $$(n + 1) $$block disk is to store the data in blocks in the first $$n $$block disk, and then store the XOR result of the data in the corresponding position on the first $$n $$block disk in the second $$(n + 1) $$block disk. This scheme can achieve the redundancy of $$1 $$hard disk. However, it is obvious that if all the hard disks do not fail, when reading data, the last disk will not be used at all, which is a waste of performance. Therefore, the current RAID5 storage method adopts the strip $$, which distributes the stored data evenly on all disks, thus improving the read-write performance.
####Hard disk and its organization
Modern hard disk can be regarded as a kind of persistent storage device which can read and write randomly by block. Most hard disks have a block size of $$512 $$bytes or $$4096 $$bytes. All blocks on the hard disk are numbered consecutively starting from $$0 $. Every time the hard disk is read or written, it should be in blocks. When reading or writing, the number of the block to be read or written is passed in, and the whole block is read or written one at a time.
RAID device can organize multiple hard disks into a certain storage structure. In the upper software, the organized storage structure looks like a whole hard disk. Therefore, the number of the block in the read-write instruction sent by the upper software to the raid should be replaced by the RAID device appropriately, and reflected in the operation of a specific hard disk or several hard disks.
####Striping and data layout
In RAID5, an important parameter is the stripe size** Stripe * * refers to continuous and equal size data blocks, which is the basic unit of RAID5 for data layout. For example, suppose that a hard disk has $$1024 $$blocks and the stripe size is $$8 $$blocks, then the hard disk is divided into a total of $$128 $$stripes, the block numbered $$[0,8) $$is on the first stripe, the block numbered $$[8,16) $$is on the second stripe, and so on. Generally, if the stripe is also numbered from 0, and the stripe size is $$s $$blocks, then the stripe number of the block with number $$B $$is $$- left / lfloor / frac {B} {s} right / rfloor $$.
For RAID5 storage with $$(n + 1) $$hard disks, we use the strip number of $$k $$on each hard disk to store the strip number of $$[kn, (K + 1) n) $(a total of $$n $). The specific storage method of the $$n $$strips is: first, according to certain rules, select a hard disk as the check disk, store the XOR sum of the $$n $$strips, and then store the $$n $$strips in other hard disks in a certain order. The rule for selecting the check disk is: with the increment of $$k $, select the check disk from the last disk in descending order until the first disk, and then start from the last disk again. The order of saving data strips is: starting from the next disk of the selected check disk, saving data strips successively until the last disk, and then starting from the first disk, saving the remaining data strips successively until the last disk of the selected check disk.
Let's take $$n = 3 $$as an example to show the strip layout.
**It is now known that the block size of these hard disks is $$4 $$bytes**
###Input format
Read in data from standard input.
The first line of input contains three positive integers, $$n $$($$n / GEQ 2 $$), $$s $$and $$l $$, representing the number of hard disks in the array, the stripe size (in blocks) of the array, and the number of existing hard disks.
The next $$l $$line contains a non negative integer separated by spaces and a string of equal length without spaces that is an integral multiple of $$8 $. This integer is the serial number of this hard disk starting from zero. The string only contains numbers * * 0 ~ 9 * * and uppercase letters * * a ~ f * *, and each two characters constitute a $$16 $$decimal number, representing one byte of hard disk content. Input hard disk set guarantee: to the hard disk has been added a number of appropriate content of the hard disk, they can just form a legal, data error free RAID5 array. Input data guarantee: the stripe size of the array can divide the size of each hard disk.
The next line contains a positive integer, $$M $, indicating the number of read operations.
The next $$M $$rows, each representing a read operation, include a non negative integer $$B_{ i} $$, which indicates the number of the block to read.
###Output format
Output to standard output.
The output contains rows of $$M $.
For each read operation, one line of output is generated. If the read operation can be carried out or calculated from the existing hard disk data, the output length of the string is $$8 $, which only contains the number * * 0 ~ 9 * * and capital letters * * a ~ f * *, and each two characters constitute a $$16 $$decimal number, indicating the content of the read data block. If the read operation cannot be performed due to one of the following conditions, a minus sign (-) is output:
-The array is incomplete, and the hard disk of the read block is missing, and the data cannot be calculated from the existing hard disk data;
-The specified block exceeds the total array length.
###Input sample 1
```in
2 1 2
0 000102030405060710111213141516172021222324252627
1 000102030405060710111213141516172021222324252627
two
0
one
```
###Output sample 1
```out
00010203
04050607
```
###Explanation of example 1
The RAID5 array is composed of two disks. The stripe size is $$1 $$block ($$4 $$bytes) long. The data of the two disks are given. Note that when RAID5 has only two disks in the array, $$p = a_{ 1} Therefore, the data in the two disks are the same, which are the contents of the RAID array. Therefore, any disk can be read.
###Input sample 2
```in
3 2 2
0 000102030405060710111213141516172021222324252627
1 A0A1A2A3A4A5A6A7B0B1B2B3B4B5B6B7C0C1C2C3C4C5C6C7
two
two
five
```
###Output sample 2
```out
A0A1A2A3
A0A0A0A0
```
###Explanation of example 2
According to the meaning of the topic, the RAID5 array is composed of three disks, the stripe size is $$2 $$block ($$8 $$bytes) long, and the data of $$0 $$and $$1 $$disks are given, and the $$2 $$disk is missing. Therefore, the layout of the whole RAID5 array is shown in the figure.
In the figure, a rectangle separated by dotted lines represents a block, and a square composed of two continuous rectangles represents a strip. When reading block No. $$2 $, the data is located in block No. $$0 $$of disk No. $$1 $, so the result is a0a1a2a3; When reading the block No. $$5 $, the data is located in the block No. $$3 $$of disk No. $$2, and the disk is missing. Therefore, it is necessary to XOR the data at the corresponding positions of the other two disks to get 14151617 $$\ oplus $$b4b5b6b7 $= $$A0.
###Data range and tips
$$2 \leq n \leq 30$$；$$ 2 \leq s \leq 100$$；$$ m \leq 30$$； The total hard disk space does not exceed $$10kib $< br>
answer：If there is no answer, please comment