package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

type FastScanner struct {
	r *bufio.Reader
}

func NewFastScanner() *FastScanner {
	return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}

func (fs *FastScanner) NextInt() int {
	sign := 1
	val := 0
	c, err := fs.r.ReadByte()
	for err == nil && (c < '0' || c > '9') && c != '-' {
		c, err = fs.r.ReadByte()
	}
	if err != nil {
		return 0
	}
	if c == '-' {
		sign = -1
		c, err = fs.r.ReadByte()
		if err != nil {
			return 0
		}
	}
	for err == nil && c >= '0' && c <= '9' {
		val = val*10 + int(c-'0')
		c, err = fs.r.ReadByte()
	}
	if err == nil {
		_ = fs.r.UnreadByte()
	}
	return sign * val
}

func existsSquareAt(T, n, m, k int, grid []int) bool {
	w := m + 1
	p := make([]int, (n+1)*w)
	need := k * k
	for i := 1; i <= n; i++ {
		rowBase := i * w
		prevRowBase := (i - 1) * w
		gridRow := (i - 1) * m
		for j := 1; j <= m; j++ {
			val := 0
			if grid[gridRow+(j-1)] <= T {
				val = 1
			}
			idx := rowBase + j
			p[idx] = val + p[prevRowBase+j] + p[rowBase+(j-1)] - p[prevRowBase+(j-1)]
			if i >= k && j >= k {
				sum := p[idx] - p[(i-k)*w+j] - p[rowBase+(j-k)] + p[(i-k)*w+(j-k)]
				if sum == need {
					return true
				}
			}
		}
	}
	return false
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	n := in.NextInt()
	m := in.NextInt()
	k := in.NextInt()
	q := in.NextInt()

	const INF = 1000000007
	grid := make([]int, n*m)
	for i := range grid {
		grid[i] = INF
	}
	times := make([]int, 0, q)
	for i := 0; i < q; i++ {
		x := in.NextInt()
		y := in.NextInt()
		t := in.NextInt()
		pos := (x-1)*m + (y - 1)
		grid[pos] = t
		times = append(times, t)
	}
	if len(times) == 0 {
		fmt.Fprintln(out, -1)
		return
	}
	sort.Ints(times)
	uniq := times[:0]
	for i, v := range times {
		if i == 0 || v != times[i-1] {
			uniq = append(uniq, v)
		}
	}

	l, r := 0, len(uniq)-1
	ans := -1
	for l <= r {
		mid := (l + r) >> 1
		if existsSquareAt(uniq[mid], n, m, k, grid) {
			ans = uniq[mid]
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	fmt.Fprintln(out, ans)
}