package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) skip() {
	for fs.idx < fs.n && fs.data[fs.idx] <= ' ' {
		fs.idx++
	}
}

func (fs *FastScanner) Int() int {
	fs.skip()
	v := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		v = v*10 + int(c-'0')
		fs.idx++
	}
	return v
}

func (fs *FastScanner) String() string {
	fs.skip()
	start := fs.idx
	for fs.idx < fs.n && fs.data[fs.idx] > ' ' {
		fs.idx++
	}
	return string(fs.data[start:fs.idx])
}

func main() {
	fs := NewFastScanner()

	n := fs.Int()
	m := fs.Int()
	k := fs.Int()

	sa := fs.String()
	sb := fs.String()

	onesA := 0
	onesB := 0
	for i := 0; i < k; i++ {
		if sa[i] == '1' {
			onesA++
		}
		if sb[i] == '1' {
			onesB++
		}
	}

	x1 := onesA
	if onesB < x1 {
		x1 = onesB
	}
	x0 := k - onesA
	if k-onesB < x0 {
		x0 = k - onesB
	}

	chosen := byte('1')
	if x0 < x1 {
		chosen = '0'
	}

	aMask := 0
	bMask := 0
	c1 := 0
	c2 := 0
	for i := 0; i < k; i++ {
		if sa[i] == chosen {
			aMask |= 1 << i
			c1++
		}
		if sb[i] == chosen {
			bMask |= 1 << i
			c2++
		}
	}

	as := make([]uint8, n)
	bs := make([]uint8, n)
	for i := 0; i < n; i++ {
		as[i] = uint8(fs.Int() - 1)
		bs[i] = uint8(fs.Int() - 1)
	}

	size := 1 << k
	inf := int32(n + 1)

	f := make([]int32, size)
	for i := 0; i < size; i++ {
		f[i] = inf
	}

	var perm [20]uint8
	for i := 0; i < k; i++ {
		perm[i] = uint8(i)
	}

	mask := aMask
	f[mask] = 0
	for i := 0; i < n; i++ {
		a := as[i]
		b := bs[i]
		p := int(perm[a])
		q := int(perm[b])
		if ((mask >> p) & 1) != ((mask >> q) & 1) {
			mask ^= (1 << p) | (1 << q)
		}
		perm[a], perm[b] = perm[b], perm[a]
		idx := int32(i + 1)
		if idx < f[mask] {
			f[mask] = idx
		}
	}

	for bit := 0; bit < k; bit++ {
		step := 1 << bit
		jump := step << 1
		for base := 0; base < size; base += jump {
			right := base + step
			for off := 0; off < step; off++ {
				i1 := base + off
				v := f[right+off]
				if v < f[i1] {
					f[i1] = v
				}
			}
		}
	}

	popc := make([]uint8, size)
	for i := 1; i < size; i++ {
		popc[i] = popc[i>>1] + uint8(i&1)
	}

	maxX := c1
	if c2 < maxX {
		maxX = c2
	}

	times := make([][]int32, maxX+1)
	if maxX > 0 {
		all := make([]int32, maxX*size)
		for x := 1; x <= maxX; x++ {
			arr := all[(x-1)*size : x*size]
			times[x] = arr
			want := uint8(x)
			for i := 0; i < size; i++ {
				if popc[i] == want {
					arr[i] = f[i]
				} else {
					arr[i] = inf
				}
			}
			for bit := 0; bit < k; bit++ {
				step := 1 << bit
				jump := step << 1
				for base := 0; base < size; base += jump {
					right := base + step
					for off := 0; off < step; off++ {
						v := arr[base+off]
						i1 := right + off
						if v < arr[i1] {
							arr[i1] = v
						}
					}
				}
			}
		}
	}

	for i := 0; i < k; i++ {
		perm[i] = uint8(i)
	}

	mask = bMask
	baseScore := k - c1 - c2
	bestScore := -1
	ansL := 1
	ansR := m

	for i := 0; i < n; i++ {
		a := as[i]
		b := bs[i]
		p := int(perm[a])
		q := int(perm[b])
		if ((mask >> p) & 1) != ((mask >> q) & 1) {
			mask ^= (1 << p) | (1 << q)
		}
		perm[a], perm[b] = perm[b], perm[a]

		r := i + 1
		if r < m {
			continue
		}

		limit := int32(r - m)
		bestX := 0
		bestI := 0
		for x := maxX; x >= 1; x-- {
			idx := times[x][mask]
			if idx <= limit {
				bestX = x
				bestI = int(idx)
				break
			}
		}

		score := baseScore + bestX + bestX
		if score > bestScore {
			bestScore = score
			ansL = bestI + 1
			ansR = r
			if score == k {
				break
			}
		}
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	fmt.Fprintln(out, bestScore)
	fmt.Fprintln(out, ansL, ansR)
	out.Flush()
}