package main

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

func readInt(in *bufio.Reader) int {
	n := 0
	b, err := in.ReadByte()
	for err == nil && (b < '0' || b > '9') {
		b, err = in.ReadByte()
	}
	for err == nil && b >= '0' && b <= '9' {
		n = n*10 + int(b-'0')
		b, err = in.ReadByte()
	}
	return n
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	n := readInt(in)
	q := readInt(in)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = readInt(in)
	}

	pref := make([][51]int32, n+1)
	for i := 0; i < n; i++ {
		pref[i+1] = pref[i]
		pref[i+1][a[i]]++
	}

	MOD := int64(998244353)
	elements := make([]int, 0, 50)
	var dp [8][64]int32

	for i := 0; i < q; i++ {
		l := readInt(in)
		r := readInt(in)

		l--
		f0 := pref[r][0] - pref[l][0]
		segLen := r - l

		if f0 > 0 {
			fmt.Fprintln(out, segLen-1, f0)
			continue
		}

		var pairs int64
		elements = elements[:0]
		for v := 1; v <= 50; v++ {
			c := int64(pref[r][v] - pref[l][v])
			if c > 1 {
				pairs += c * (c - 1) / 2
			} else if c == 1 {
				elements = append(elements, v)
			}
		}

		if pairs > 0 {
			fmt.Fprintln(out, segLen-2, pairs%MOD)
			continue
		}

		dp = [8][64]int32{}
		dp[0][0] = 1
		max_i := 0
		for _, x := range elements {
			for k := max_i; k >= 0; k-- {
				dpi := &dp[k]
				dpi1 := &dp[k+1]
				for j := 0; j < 64; j++ {
					if v := dpi[j]; v > 0 {
						dpi1[j^x] += v
					}
				}
			}
			if max_i < 6 {
				max_i++
			}
		}

		found := false
		for k := 3; k <= 7; k++ {
			if dp[k][0] > 0 {
				fmt.Fprintln(out, segLen-k, int64(dp[k][0])%MOD)
				found = true
				break
			}
		}

		if !found {
			fmt.Fprintln(out, -1)
		}
	}
}