Problem: Omkar has a pie tray with k (2 ≤ k ≤ 20) spots. Each spot in the tray contains either a chocolate pie or a pumpkin pie. However, Omkar does not like the way that the pies are currently arranged, and has another ideal arrangement that he would prefer instead.

To assist Omkar, n elves have gathered in a line to swap the pies in Omkar's tray. The j-th elf from the left is able to swap the pies at positions a_j and b_j in the tray.

In order to get as close to his ideal arrangement as possible, Omkar may choose a contiguous subsegment of the elves and then pass his pie tray through the subsegment starting from the left. However, since the elves have gone to so much effort to gather in a line, they request that Omkar's chosen segment contain at least m (1 ≤ m ≤ n) elves.

Formally, Omkar may choose two integers l and r satisfying 1 ≤ l ≤ r ≤ n and r - l + 1 ≥ m so that first the pies in positions a_l and b_l will be swapped, then the pies in positions a_{l + 1} and b_{l + 1} will be swapped, etc. until finally the pies in positions a_r and b_r are swapped.

Help Omkar choose a segment of elves such that the amount of positions in Omkar's final arrangement that contain the same type of pie as in his ideal arrangement is the maximum possible. Note that since Omkar has a big imagination, it might be that the amounts of each type of pie in his original arrangement and in his ideal arrangement do not match.

Input

The first line contains three integers n, m, and k (1 ≤ m ≤ n ≤ 10^6 and 2 ≤ k ≤ 20) — the number of elves, the minimum subsegment length, and the number of spots in Omkar's tray respectively. 

The second and third lines each contain a string of length k consisting of 0s and 1s that represent initial arrangement of pies and ideal arrangement of pies; the j-th character in each string is equal to 0 if the j-th spot in the arrangement contains a chocolate pie and is equal to 1 if the j-th spot in the arrangement contains a pumpkin pie. It is not guaranteed that the two strings have the same amount of 0s or the same amount of 1s.

n lines follow. The j-th of these lines contains two integers a_j and b_j (1 ≤ a_j, b_j ≤ k, a_j ≠ b_j) which indicate that the j-th elf from the left can swap the pies at positions a_j and b_j in the tray.

Output

Output two lines. 

The first line should contain a single integer s (0 ≤ s ≤ k) equal to the amount of positions that contain the same type of pie in Omkar's final arrangement and in Omkar's ideal arrangement; s should be the maximum possible. 

The second line should contain two integers l and r satisfying 1 ≤ l ≤ r ≤ n and r - l + 1 ≥ m, indicating that Omkar should pass his tray through the subsegment l, l + 1, ..., r to achieve a final arrangement with s positions having the same type of pie as his ideal arrangement.

If there are multiple answers you may output any of them.

Examples

Input


4 2 5
11000
00011
1 3
3 5
4 2
3 4


Output


5
1 3


Input


4 3 5
11000
00011
1 3
1 5
2 4
1 5


Output


3
1 4

Note

In the first test case, the swaps will go like this: 

  * Swap 1 and 3: 11000 becomes 01100
  * Swap 3 and 5: 01100 becomes 01001
  * Swap 4 and 2: 01001 becomes 00011

The final arrangement is the same as the ideal arrangement 00011, so there are 5 positions with the same type of pie, which is optimal.

In the second test case, the swaps will go like this: 

  * Swap 1 and 3: 11000 becomes 01100
  * Swap 1 and 5: 01100 becomes 01100
  * Swap 4 and 2: 01100 becomes 00110
  * Swap 1 and 5: 00110 becomes 00110

The final arrangement has 3 positions with the same type of pie as the ideal arrangement 00011, those being positions 1, 2, and 4. In this case the subsegment of elves (l, r) = (2, 3) is more optimal, but that subsegment is only length 2 and therefore does not satisfy the constraint that the subsegment be of length at least m = 3.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.stream.IntStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            GOmkarAndPies solver = new GOmkarAndPies();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class GOmkarAndPies {
        Debug debug = new Debug(true);
        int k;

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int m = in.readInt();
            k = in.readInt();
            int src = 0;
            int dst = 0;
            for (int i = 0; i < k; i++) {
                src |= (in.readChar() - '0') << i;
            }
            for (int i = 0; i < k; i++) {
                dst |= (in.readChar() - '0') << i;
            }
            int[][] pairs = new int[2][n];
            for (int i = n - 1; i >= 0; i--) {
                for (int j = 0; j < 2; j++) {
                    pairs[j][i] = in.readInt() - 1;
                }
            }

            int[] a = new int[n];
            int[] b = new int[n];
            int[] perm = IntStream.range(0, k).toArray();
            int[] invPerm = perm.clone();
            for (int i = 0; i < n; i++) {
                swap(perm, pairs[0][i], pairs[1][i]);
                inv(perm, invPerm);
                a[i] = perm(invPerm, src);
                if (i + 1 < n) {
                    b[i + 1] = perm(invPerm, dst);
                }
                //a[i] = Bits.swap(i == 0 ? src : a[i - 1], pairs[0][i], pairs[1][i]);
            }
            b[0] = dst;
//        for (int i = 0; i < n - 1; i++) {
//            applyLeft(invPerm, pairs[0][i], pairs[1][i]);
//            b[i + 1] = perm(invPerm, dst);
//        }

            int[] L = new int[1 << k];
            int[] R = new int[1 << k];
            Arrays.fill(L, -1);
            Arrays.fill(R, -1);

            for (int i = 0; i < n; i++) {
                add(L, b[i], i);
                add(R, a[n - i - 1], n - i - 1);
            }
//        for (int i = 0; i < n; i++) {
//            debug.debug("a[" + i + "]", toString(k, a[i]));
//            debug.debug("b[" + i + "]", toString(k, b[i]));
//        }
//        for (int i = 0; i < n; i++) {
//            for (int j = i; j < n; j++) {
//                int cast = apply(pairs, i, j, src);
//                int common = Integer.bitCount(cast & dst);
//                int calc = Integer.bitCount(a[j] & b[i]);
//                if(common != calc){
//                    throw new RuntimeException();
//                }
//            }
//        }

            debug.debug("a", a);
            debug.debug("b", b);
            //debug.debug("L", L);
            //debug.debug("R", R);
            int ans = -1;
            int l = -1;
            int r = -1;
            for (int i = 0; i < 1 << k; i++) {
                if (L[i] == -1 || R[i] == -1) {
                    continue;
                }
                if (R[i] - L[i] + 1 < m) {
                    continue;
                }
                int bitcount = Integer.bitCount(i);
                if (ans < bitcount) {
                    ans = bitcount;
                    l = L[i];
                    r = R[i];
                }
            }
            debug.debug("ans", ans);
            debug.debug("l", l);
            debug.debug("r", r);


            out.println(k - (Integer.bitCount(src) - ans) - (Integer.bitCount(dst) - ans));
            out.append(mirror(r, n) + 1).append(' ').append(mirror(l, n) + 1);
        }

        public int mirror(int i, int n) {
            return n - 1 - i;
        }

        public void add(int[] core, int x, int id) {
            if (core[x] != -1) {
                return;
            }
            core[x] = id;
            for (int i = 0; i < k; i++) {
                if (Bits.get(x, i) == 1) {
                    add(core, Bits.clear(x, i), id);
                }
            }
        }

        public void swap(int[] perm, int a, int b) {
            SequenceUtils.swap(perm, a, b);
        }

        public void inv(int[] perm, int[] output) {
            for (int i = 0; i < perm.length; i++) {
                output[perm[i]] = i;
            }
        }

        public int perm(int[] p, int x) {
            int ans = 0;
            for (int i = 0; i < p.length; i++) {
                ans |= Bits.get(x, p[i]) << i;
            }
            return ans;
        }

    }

    static class Debug {
        private boolean offline;
        private PrintStream out = System.err;
        static int[] empty = new int[0];

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager() == null;
        }

        public Debug debug(String name, int x) {
            if (offline) {
                debug(name, "" + x);
            }
            return this;
        }

        public Debug debug(String name, String x) {
            if (offline) {
                out.printf("%s=%s", name, x);
                out.println();
            }
            return this;
        }

        public Debug debug(String name, Object x) {
            return debug(name, x, empty);
        }

        public Debug debug(String name, Object x, int... indexes) {
            if (offline) {
                if (x == null || !x.getClass().isArray()) {
                    out.append(name);
                    for (int i : indexes) {
                        out.printf("[%d]", i);
                    }
                    out.append("=").append("" + x);
                    out.println();
                } else {
                    indexes = Arrays.copyOf(indexes, indexes.length + 1);
                    if (x instanceof byte[]) {
                        byte[] arr = (byte[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof short[]) {
                        short[] arr = (short[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof boolean[]) {
                        boolean[] arr = (boolean[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof char[]) {
                        char[] arr = (char[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof int[]) {
                        int[] arr = (int[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof float[]) {
                        float[] arr = (float[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof double[]) {
                        double[] arr = (double[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof long[]) {
                        long[] arr = (long[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else {
                        Object[] arr = (Object[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    }
                }
            }
            return this;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public char readChar() {
            skipBlank();
            char c = (char) next;
            next = read();
            return c;
        }

    }

    static class SequenceUtils {
        public static void swap(int[] data, int i, int j) {
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

    }

    static class Bits {
        private Bits() {
        }

        public static int get(int x, int i) {
            return (x >>> i) & 1;
        }

        public static int clear(int x, int i) {
            return x & (~(1 << i));
        }

    }
}