Walf Wear

View as PDF

Submit solution

Points: 15
Time limit: 2.0s
Memory limit: 128M

Problem types

Walf's clothes have N possible colors, labelled from 1 to N. His top clothing rack has N hats, the i-th hat having a color of h_i. His bottom clothing rack has N shirts, the i-th shirt having a color of s_i. No two hats have the same color and no two shirts have the same color.

The colors of hats on the rack are given by h_1, h_2, \dots, h_N and color of his shirts are given by s_1, s_2, \dots, s_N. These values are fixed and regardless of what Walf wears, his racks will reset to this state at the end of the day.

Each morning, Walf picks a hat and a shirt to wear (for obvious reasons, he only wears blue jeans). To help him decide, his friend Fax restricts his hat choices to h_a, h_{a + 1}, \dots, h_{b - 1}, h_b and his shirt choices to s_c, s_{c + 1}, \dots, s_{d - 1}, h_d. The values of a, b, c, and d change from day to day.

There are D days in total. For each day, output if it's possible that Walf wears the same color hat and shirt. More formally, output if there's some a \leq x \leq b and c \leq y \leq d such that h_x = s_y.


  • N, D \leq 100\ 000
  • 1 \leq s_i, p_i \leq N
  • The values of h_i are all unique
  • The values of s_i are all unique
  • 1 \leq a \leq b \leq N
  • 1 \leq c \leq d \leq N

Input Specification

The first line of input will contain two numbers, N and D.

The second line of input will contain N numbers, the ith number is h_i.

The third line of input will contain N numbers, the ith number is s_i.

The next D lines will contain 4 numbers each, each line containing the values of a, b, c, and d for that day.

Output Specification

Output one line with D characters. The j-th character should be Y if Walf can wear the same color hat and shirt on Day j and N if he can't.

Sample Input

5 3
3 5 2 1 4
5 2 1 4 3
1 5 1 5
1 2 3 5
1 3 3 4

Sample Output



There are no comments at the moment.