아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

광부

시간 제한1초메모리 제한256 MB

요약
n개의 구간과 m개의 점이 주어질 때, 교집합이 주어진 점 중 하나 이상을 포함하는 공집합이 아닌 구간 부분집합의 개수를 998244353으로 나눈 나머지로 구한다.
난이도

어려움10점 중 8점

유형
구간, 정렬, 조합론, 투 포인터
정답자
아직 제출이 없습니다

문제

광산에는 서로 다른 nn종류의 광물이 있다. 광산은 좌표축으로 나타낼 수 있고, ii번째 광물은 구간 [li,ri][l_i, r_i] 안의 어느 위치에서든 캘 수 있다.

당신은 이 광산에서 일하는 광부이다. 매일 감독관은 광물을 캐는 작업을 하나씩 준다. 작업은 서로 다른 광물로 이루어진 공집합이 아닌 집합이며(모두 2n−12^n - 1가지가 있다), 목표는 그 집합에 들어 있는 광물을 전부 모으는 것이다.

광산에는 mm개의 안전한 위치 aia_i가 있다. 어떤 작업이 쉬운 작업이라는 것은, 안전한 위치 apa_p를 하나 골라 그곳에서 필요한 광물을 모두 캘 수 있다는 뜻이다.

이제 쉬운 작업의 개수를 세려고 한다.

입력

첫째 줄에 두 정수 nn과 mm이 주어진다(1≤n,m≤1051 \le n, m \le 10^5).

그다음 nn개의 줄이 주어지고, 각 줄에는 두 정수 lil_i와 rir_i가 있다(1≤li≤ri≤1091 \le l_i \le r_i \le 10^9).

그다음 mm개의 줄이 주어지고, 각 줄에는 정수 aia_i가 하나씩 있다(1≤ai≤1091 \le a_i \le 10^9).

출력

쉬운 작업의 개수를 998 244 353998\,244\,353으로 나눈 나머지를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    3 2
    7 11
    1 5
    3 8
    4
    7
    
    예상 출력
    5