module z_algorithm
contains
  function character_z_algorithm(s) result(res)
    character(*) :: s
    integer :: res(len_trim(s)), n, i, j, k
    res = 0
    n = len_trim(s)
    res(1) = n
    i = 1
    j = 0
    do while (i < n)
      do while (i + j < n .and. s(j + 1:j + 1) == s(i + j + 1:i + j + 1))
        j = j + 1
      end do
      res(i + 1) = j
      if (j == 0) then
        i = i + 1
        cycle
      end if
      k = 1
      do while (i + k < n .and. k + res(k + 1) < j)
        res(i + k + 1) = res(k + 1)
        k = k + 1
      end do
      i = i + k
      j = j - k
    end do
  end
  function integer_z_algorithm(s) result(res)
    integer :: s(:)
    integer :: res(size(s)), n, i, j, k
    res = 0
    n = size(s)
    res(1) = n
    i = 1
    j = 0
    do while (i < n)
      do while (i + j < n .and. s(j + 1) == s(i + j + 1))
        j = j + 1
      end do
      res(i + 1) = j
      if (j == 0) then
        i = i + 1
        cycle
      end if
      k = 1
      do while (i + k < n .and. k + res(k + 1) < j)
        res(i + k + 1) = res(k + 1)
        k = k + 1
      end do
      i = i + k
      j = j - k
    end do
  end
end module z_algorithm
program xor_shift
  use z_algorithm
  implicit none
  integer :: n, i
  integer, dimension(200000) :: a = 0, b = 0
  integer, dimension(600000) :: s = 0, z = 0
  read(*,*) n
  read(*,*) a(1:n)
  read(*,*) b(1:n)
  do i = 1, n - 1
    s(i) = xor(b(i), b(i + 1))
    s(i + n) = xor(a(i), a(i + 1))
  end do
  s(n) = xor(b(n), b(1))
  s(2 * n) = xor(a(n), a(1))
  do i = 1, n - 1
    s(i + 2 * n) = s(i + n)
  end do
  z(1:3 * n - 1) = integer_z_algorithm(s(1:3 * n - 1))
  do i = 1, n
    if (z(i + n) >= n) then
      write(*,'(i0,x,i0)') i - 1, xor(a(i), b(1))
    end if
  end do
end program xor_shift