```go
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"sort"
)

const INF int64 = 1e18

type Item struct {
	val int64
	b   int
	i   int
}

type PQ []Item

func (pq PQ) Len() int           { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].val < pq[j].val }
func (pq PQ) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) {
	*pq = append(*pq, x.(Item))
}
func (pq *PQ) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

type Segment struct {
	l, r int
	id   int
}

type Terminal struct {
	u   int
	len int
}

type Query struct {
	id  int
	u   int
	len int
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, m int
	fmt.Fscan(reader, &n, &m)

	initials := make([]Segment, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &initials[i].l, &initials[i].r)
		initials[i].id = i
	}

	terms := make([]Segment, m)
	for i := 0; i < m; i++ {
		fmt.Fscan(reader, &terms[i].l, &terms[i].r)
		terms[i].id = i
	}

	ans := make([]int64, n)
	for i := 0; i < n; i++ {
		ans[i] = -1
	}

	for parity := 0; parity < 2; parity++ {
		var queries []Query
		for _, s := range initials {
			if (s.r-s.l)%2 == parity {
				u := (s.l + s.r) / 2
				if parity == 1 {
					u = (s.l + s.r - 1) / 2
				}
				queries = append(queries, Query{s.id, u, s.r - s.l})
			}
		}

		var terminals []Terminal
		for _, s := range terms {
			if (s.r-s.l)%2 == parity {
				u := (s.l + s.r) / 2
				if parity == 1 {
					u = (s.l + s.r - 1) / 2
				}
				terminals = append(terminals, Terminal{u, s.r - s.l})
			}
		}

		if len(queries) == 0 {
			continue
		}

		var uList []int
		for _, t := range terminals {
			uList = append(uList, t.u)
		}
		sort.Ints(uList)
		var uUnique []int
		for _, u := range uList {
			if len(uUnique) == 0 || uUnique[len(uUnique)-1] != u {
				uUnique = append(uUnique, u)
			}
		}

		type Block struct {
			uStart int
			A      []int64
		}
		var blocks []Block
		type Pos struct{ b, i int }
		mapU := make(map[int]Pos)

		if len(uUnique) > 0 {
			start := uUnique[0]
			prev := uUnique[0]
			for i := 1; i < len(uUnique); i++ {
				if uUnique[i]-prev > 2 {
					blocks = append(blocks, Block{start, make([]int64, prev-start+1)})
					start = uUnique[i]
				}
				prev = uUnique[i]
			}
			blocks = append(blocks, Block{start, make([]int64, prev-start+1)})
		}

		for b := range blocks {
			for i := range blocks[b].A {
				blocks[b].A[i] = INF
				u := blocks[b].uStart + i
				mapU[u] = Pos{b, i}
			}
		}

		sort.Slice(terminals, func(i, j int) bool {
			return terminals[i].len < terminals[j].len
		})
		sort.Slice(queries, func(i, j int) bool {
			return queries[i].len < queries[j].len
		})

		pq := make(PQ, 0)
		heap.Init(&pq)

		termIdx := 0
		for _, q := range queries {
			for termIdx < len(terminals) && terminals[termIdx].len <= q.len {
				t := terminals[termIdx]
				termIdx++
				pos, ok := mapU[t.u]
				if !ok {
					continue
				}
				val := int64(-t.len)
				if val < blocks[pos.b].A[pos.i] {
					blocks[pos.b].A[pos.i] = val
					heap.Push(&pq, Item{val, pos.b, pos.i})
				}
			}

			for pq.Len() > 0 {
				item := heap.Pop(&pq).(Item)
				if item.val != blocks[item.b].A[item.i] {
					continue
				}
				b := item.b
				i := item.i
				K := len(blocks[b].A)

				if i-1 > 0 {
					newVal := max(blocks[b].A[i-2], blocks[b].A[i])
					if newVal < blocks[b].A[i-1] {
						blocks[b].A[i-1] = newVal
						heap.Push(&pq, Item{newVal, b, i - 1})
					}
				}
				if i+1 < K-1 {
					newVal := max(blocks[b].A[i], blocks[b].A[i+2])
					if newVal < blocks[b].A[i+1] {
						blocks[b].A[i+1] = newVal
						heap.Push(&pq, Item{newVal, b, i + 1})
					}
				}
			}

			pos, ok := mapU[q.u]
			if !ok || blocks[pos.b].A[pos.i] == INF {
				ans[q.id] = -1
			} else {
				v := (int64(q.len) + blocks[pos.b].A[pos.i]) / 2
				if v < 0 {
					ans[q.id] = -1
				} else {
					ans[q.id] = v
				}
			}
		}
	}

	out := bufio.NewWriter(os.Stdout)
	for i := 0; i < n; i++ {
		fmt.Fprint(out, ans[i])
		if i < n-1 {
			fmt.Fprint(out, " ")
		}
	}
	fmt.Fprintln(out)
	out.Flush()
}
```