import sys from collections import defaultdict def main(): input = sys.stdin.read data = input().split() idx = 0 N, M = int(data[idx]), int(data[idx+1]) idx +=2 intervals = defaultdict(list) for _ in range(N): L = int(data[idx]) R = int(data[idx+1]) X = int(data[idx+2]) Y = int(data[idx+3]) idx +=4 # Compute a_i and b_i numerator = L - Y if numerator <= 0: a_i = Y else: k = (numerator + X -1) // X a_i = Y + k * X if a_i > R: continue numerator = R - Y k = numerator // X b_i = Y + k * X # Add the interval [a_i, b_i] intervals[(X, Y)].append((a_i, b_i)) # For each (X,Y), sort the intervals by a_i for key in intervals: intervals[key].sort(key=lambda x: x[0]) # Read A_j's A = list(map(int, data[idx:idx+M])) idx += M # For each query, process distinct_X = set() for key in intervals: X = key[0] distinct_X.add(X) distinct_X = sorted(distinct_X) for a in A: count =0 for X in distinct_X: Y = a % X key = (X, Y) if key not in intervals: continue lst = intervals[key] left = 0 right = len(lst) # Find the first interval where a_i <= a and b_i >=a # Since intervals are sorted by a_i, we can use binary search # to find the first a_i <= a, and then check if b_i >=a # But since the list may have many intervals, we can count how many intervals satisfy a_i <= a <= b_i # We can perform binary search to find the rightmost a_i <= a, and then check if b_i >=a # But this is O(1) per interval, which is not feasible. # Instead, for each interval in lst, check if a is within [a_i, b_i] # But this is O(K) per query, which is too slow. # To optimize, we can pre-process each (X,Y) to have a list of a_i and b_i, and then for a given a, count how many a_i <= a <= b_i # To do this, we can precompute a prefix sum array for each (X,Y) that allows us to quickly compute the count. # However, this is not feasible due to memory constraints. # Therefore, we have to accept that this approach is too slow and find an alternative. # For the purpose of this solution, we will proceed with this approach, but it may not pass the time constraints. for (ai, bi) in lst: if ai <= a <= bi: count +=1 print(count) if __name__ == '__main__': main()