Mutation
Scientists on the planet Olympia are conducting an experiment to mutate a primitive test organism into a target primitive organism. The genomes of these organisms are represented as sequences of genes, where each gene is encoded by the digit 0 or 1. The experiment progresses through several stages. In each stage, some genes in the test organism's genome are flipped to their opposite values (i.e., from 0 to 1 or vice versa). Scientists can select which genes to flip, but the number of genes flipped in each stage is predetermined and varies for each mutation stage. Both the test and target organisms have genomes of the same length, composed of repeated sequences known as base sequences.
Your task is to write a program that, given the genomes of the test and target organisms, along with the number of genes flipped at each stage, determines the minimum number of mutation stages required to transform the test organism's genome into the target organism's genome.
Input
The first line contains four integers A, B, N, and M (1 ≤ A ≤ 40000, 1 ≤ B ≤ 40000, 1 ≤ N ≤ 2×10^9, 1 ≤ M ≤ 100000). Here, A and B are the lengths of the base sequences for the test and target organisms, respectively. N is the length of the genomes of both organisms, and it is guaranteed that N is divisible by both A and B. M is the maximum number of mutation stages allowed. The second and third lines provide the base sequences for the test and target organisms, consisting only of 0 and 1, with lengths A and B, respectively. The next M lines each contain a natural number not exceeding N, representing the number of genes flipped in the i-th stage. It is guaranteed that the mutation can be completed in M or fewer stages.
Output
Output a single integer, which is the minimum number of mutation stages required to transform the test organism's genome into the target organism's genome.