```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

var (
	reader  *bufio.Reader
	writer  *bufio.Writer
	queries int
	S       = 1000000
)

func query(x, y int) string {
	fmt.Fprintf(writer, "%d %d\n", x, y)
	writer.Flush()
	queries++
	resp, _ := reader.ReadString('\n')
	resp = strings.TrimSpace(resp)
	if strings.HasSuffix(resp, "!") {
		os.Exit(0)
	}
	return resp
}

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)

	query(0, 0)
	samePhrase := query(0, 0)

	var closerPhrase, furtherPhrase string

	r1 := query(1, 0)
	r2 := query(2, 0)

	if r1 != samePhrase && r2 != samePhrase && r1 != r2 {
		closerPhrase = r1
		furtherPhrase = r2
	} else {
		r3 := query(S, 0)
		r4 := query(S-1, 0)
		r5 := query(S-2, 0)

		if r4 != samePhrase && r5 != samePhrase && r4 != r5 {
			closerPhrase = r4
			furtherPhrase = r5
		} else if r1 == r4 && r1 != samePhrase {
			closerPhrase = r1
			if r3 == r1 {
				furtherPhrase = r2 
			} else {
				furtherPhrase = r3
			}
		} else {
			ry1 := query(0, 1)
			ry2 := query(0, 2)
			if ry1 != samePhrase && ry2 != samePhrase && ry1 != ry2 {
				closerPhrase = ry1
				furtherPhrase = ry2
			} else {
				ry3 := query(0, S)
				ry4 := query(0, S-1)
				ry5 := query(0, S-2)
				if ry4 != samePhrase && ry5 != samePhrase && ry4 != ry5 {
					closerPhrase = ry4
					furtherPhrase = ry5
				} else if ry1 == ry4 && ry1 != samePhrase {
					closerPhrase = ry1
					if ry3 == ry1 {
						furtherPhrase = ry2
					} else {
						furtherPhrase = ry3
					}
				} else {
					query(S, 0)
					query(0, S)
					query(S, S)
					os.Exit(0)
				}
			}
		}
	}

	if furtherPhrase == "" {
		if closerPhrase == r1 {
			furtherPhrase = r2
		} else {
			furtherPhrase = r1
		}
	}

	lx, rx := 0, S
	ly, ry := 0, S
	px, py := 0, 0
	query(px, py)

	for lx < rx || ly < ry {
		var qx, qy int
		canX := false
		if lx < rx {
			qx = lx + rx - px
			if qx >= 0 && qx <= S {
				canX = true
			}
		}

		var canY bool
		if ly < ry {
			qy = ly + ry - py
			if qy >= 0 && qy <= S {
				canY = true
			}
		}

		if canX {
			resp := query(qx, py)
			midX := (lx + rx) / 2
			if resp == samePhrase {
				lx, rx = midX, midX
			} else if resp == closerPhrase {
				if qx > px {
					lx = midX + 1
				} else {
					rx = midX
				}
			} else {
				if qx > px {
					rx = midX
				} else {
					lx = midX + 1
				}
			}
			px = qx
			continue
		}

		if canY {
			resp := query(px, qy)
			midY := (ly + ry) / 2
			if resp == samePhrase {
				ly, ry = midY, midY
			} else if resp == closerPhrase {
				if qy > py {
					ly = midY + 1
				} else {
					ry = midY
				}
			} else {
				if qy > py {
					ry = midY
				} else {
					ly = midY + 1
				}
			}
			py = qy
			continue
		}

		nx, ny := px, py
		if lx < rx {
			nx = lx + rx - px
		}
		if ly < ry {
			ny = ly + ry - py
		}
		query(nx, ny)
		px, py = nx, ny
	}

	query(lx, ly)
}
```