Compare substring - MarisaOJ: Marisa Online Judge

Given a string

$S=S_1S_2...S_n$ of length

$n$ that contains only digits. There are

$q$ queries, each of the form

$(a, b, l)$ . Determine which number is greater

$S[a...a+l]$ or

$S[b...b+l]$ . ### Input - The first line contains a string

$S$ . - The second line contains an integer

$q$ . - The next

$q$ lines, each line contains 3 integers

$a, b, l$ , a query. ### Output - Print: +

$>$ if

$S[a...a+l]$ is greater than

$S[b...b+l]$ . +

$<$ if

$S[a...a+l]$ is smaller than

$S[b...b+l]$ . +

$=$ if

$S[a...a+l]$ is equal to

$S[b...b+l]$ . ### Constraints -

$1 \le |S|, q \le 10^5$ . -

$1 \le a, b \le |S|$ . -

$a + l, b + l \le |S|$ . ### Example Input:

$0139291 3 4 6 1 1 2 5 2 7 0$

Output:

$>$ \

$<$ \

$=$

Topic

Binary search

String

Hashing

Rating

1200

Solution (0)

Solution