Fast io }

import [Link].*; return [Link]();

import [Link].*; }
}
public class Main {
static class FastScanner { public static void main(String[] args) throws
private final byte[] buffer = new byte[1 << Exception {
16]; FastScanner fs = new
private int ptr = 0, len = 0; FastScanner([Link]);
private final InputStream in; StringBuilder out = new StringBuilder();

FastScanner(InputStream in) { int t = 1; // [Link]();

[Link] = in; while (t-- > 0) {
} // solve here
}
int read() throws IOException {
if (ptr >= len) { [Link]([Link]());
len = [Link](buffer); }
ptr = 0; }
if (len <= 0) return -1;
} Math utilities
return buffer[ptr++]; static long gcd(long a, long b) {
} return b == 0 ? a : gcd(b, a % b);
}
int nextInt() throws IOException {
int c, sgn = 1, res = 0; static long lcm(long a, long b) {
do { c = read(); } while (c <= ' '); return a / gcd(a, b) * b;
if (c == '-') { sgn = -1; c = read(); } }
while (c > ' ') {
res = res * 10 + (c - '0'); static long mod = 1_000_000_007;
c = read();
} static long modPow(long a, long e) {
return res * sgn; long r = 1;
} while (e > 0) {
if ((e & 1) == 1) r = r * a % mod;
long nextLong() throws IOException { a = a * a % mod;
int c, sgn = 1; e >>= 1;
long res = 0; }
do { c = read(); } while (c <= ' '); return r;
if (c == '-') { sgn = -1; c = read(); } }
while (c > ' ') {
res = res * 10 + (c - '0'); Arrays & Prefix
c = read(); long[] pref = new long[n + 1];
} for (int i = 0; i < n; i++)
return res * sgn; pref[i + 1] = pref[i] + arr[i];
}
// sum l..r (0-indexed)
String next() throws IOException { long sum = pref[r + 1] - pref[l];
int c;
StringBuilder sb = new StringBuilder(); Graph (Adj List + DFS/BFS)
do { c = read(); } while (c <= ' '); ArrayList<Integer>[] g = new ArrayList[n];
while (c > ' ') { for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
[Link]((char) c);
c = read(); boolean[] vis = new boolean[n];
 dfs1(v, u);
void dfs(int u) { sub[u] += sub[v];
vis[u] = true; }
for (int v : g[u])
}
if (!vis[v]) dfs(v);
}
void dfs2(int u, int p) {
Queue<Integer> q = new ArrayDeque<>(); for (int v : g[u]) {
[Link](src); if (v == p) continue;
vis[src] = true;
sub[u] -= sub[v];
while (![Link]()) {
sub[v] += sub[u];
int u = [Link]();
for (int v : g[u]) {
if (!vis[v]) { dfs2(v, u);
vis[v] = true;
[Link](v); sub[v] -= sub[u];
} sub[u] += sub[v];
}
}
}
}

TREE DP PATTERNS (Java) 3️⃣ DP with 2 states (take / not take)

1️⃣ Subtree DP (bottom-up) Classic tree independent set

dp[u] depends on children int[][] dp; // dp[u][0/1]

ArrayList<Integer>[] g; void dfs(int u, int p) {

int[] dp; dp[u][0] = 0;
dp[u][1] = 1;
void dfs(int u, int p) {
dp[u] = 1; // base for (int v : g[u]) {
for (int v : g[u]) { if (v == p) continue;
if (v == p) continue; dfs(v, u);
dfs(v, u); dp[u][0] +=
dp[u] += dp[v]; // example: [Link](dp[v][0], dp[v][1]);
subtree size dp[u][1] += dp[v][0];
} }
} }

2️⃣ Rerooting DP 4️⃣ Tree diameter (2 DFS trick)

int far, dist;
compute dp for all roots void dfs(int u, int p, int d) {
if (d > dist) { dist = d; far =
int[] sub, ans; u; }
for (int v : g[u])
void dfs1(int u, int p) { if (v != p) dfs(v, u, d +
sub[u] = 1; 1);
for (int v : g[u]) { }
if (v == p) continue; // dfs(0,-1,0); dfs(far,-1,0);
 }

🌐 GRAPH PATTERNS }

4️⃣ Dijkstra (weighted graph)

1️⃣ BFS shortest path (unweighted)
long[] dist = new long[n];
int[] dist = new int[n];
[Link](dist, Long.MAX_VALUE);
[Link](dist, -1);
PriorityQueue<long[]> pq = new
Queue<Integer> q = new
PriorityQueue<>([Link]
ArrayDeque<>();
Long(a -> a[0]));

dist[s] = 0;
dist[s] = 0;
[Link](s);
[Link](new long[]{0, s});

while (![Link]()) {
while (![Link]()) {
int u = [Link]();
long[] cur = [Link]();
for (int v : g[u]) {
long d = cur[0];
if (dist[v] == -1) {
int u = (int) cur[1];
dist[v] = dist[u] + 1;
if (d != dist[u]) continue;
[Link](v);
}
for (long[] e : g[u]) {
}
int v = (int) e[0];
}
long w = e[1];
if (dist[v] > d + w) {
2️⃣ DFS cycle detection (undirected)
dist[v] = d + w;
boolean dfs(int u, int p) { [Link](new
vis[u] = true; long[]{dist[v], v});
for (int v : g[u]) { }
if (v == p) continue; }
if (vis[v] || dfs(v, u)) }
return true;
} 🧠 BIT OPERATIONS (VERY IMPORTANT)
return false;
} 1️⃣ Basics
x & 1 // check odd
3️⃣ Topological Sort (DAG) x << k // multiply by 2^k
int[] indeg = new int[n]; x >> k // divide by 2^k
Queue<Integer> q = new x & (x - 1) // remove lowest set
ArrayDeque<>(); bit

for (int i = 0; i < n; i++) 2️⃣ Check / Set / Unset bit

if (indeg[i] == 0) [Link](i); boolean on = ((mask >> i) & 1) == 1;
mask |= (1 << i); // set
while (![Link]()) { mask &= ~(1 << i); // unset
int u = [Link](); mask ^= (1 << i); // toggle
for (int v : g[u]) {
if (--indeg[v] == 0) 3️⃣ Iterate over all subsets
[Link](v);
for (int sub = mask; sub > 0; sub = Space optimized:​
(sub - 1) & mask) { dp[w] = max(dp[w], dp[w - wi] + vi)
// sub is subset of mask
} ▶ Unbounded Knapsack
dp[w] = max(dp[w], dp[w - wi] + vi)
4️⃣ Count set bits
int c = [Link](x); ▶ Grid DP
dp[i][j] = dp[i-1][j] + dp[i][j-1]
5️⃣ Bitmask DP (subset DP)
int N = 1 << n; With obstacle:​
if blocked → dp = 0
int[] dp = new int[N];
[Link](dp, INF);
dp[0] = 0; 3️⃣ Subsequence / String DP​
for (int mask = 0; mask < N; mask++) ▶ LCS
{ if s[i]==t[j]:
for (int i = 0; i < n; i++) { dp[i][j] = dp[i-1][j-1] + 1
if ((mask & (1 << i)) == 0) else:
{ dp[i][j] = max(dp[i-1][j],
dp[mask | (1 << i)] = dp[i][j-1])
[Link](dp[mask | ▶ Edit Distance
(1 << i)], dp[mask] + cost[i]); dp[i][j] = min(
} dp[i-1][j] + 1, // delete
} dp[i][j-1] + 1, // insert
} dp[i-1][j-1] + cost //
replace
📘 COMMON DP TRANSITION FORMULAS )
(CP CHEAT SHEET)
4️⃣ Interval DP​
1️⃣ 1D DP (Linear)
▶ Merge / Split

▶ Take / Skip dp[l][r] = min over k in [l,r):

dp[l][k] + dp[k+1][r] +
dp[i] = max(dp[i-1], dp[i-2] + a[i])
👉 House robber, no adjacent
cost(l,r)​
👉 Matrix chain, stone merging

▶ Prefix choice​
▶ Game DP
dp[i] = min over j<i (dp[j] +
cost(j+1..i)) dp[l][r] = max(
a[l] - dp[l+1][r],
▶ Count ways a[r] - dp[l][r-1]
)​
dp[i] = dp[i-1] + dp[i-2]
​
5️⃣ Tree DP (Recap)​
​ ▶ Combine children
2️⃣ 2D DP (Classic) dp[u] = base
for v in children:
▶ Knapsack (0/1) dp[u] = combine(dp[u], dp[v])
dp[i][w] = max(dp[i-1][w],
dp[i-1][w - wi] + vi) ▶ Two states (pick / not pick)
dp[u][1] = val[u] + Σ dp[v][0]
dp[u][0] = Σ max(dp[v][0], dp[v][1]) int bit = xr & -xr;
int x = 0, y = 0;
6️⃣ Bitmask DP​
▶ Add element for (int v : a) {
if ((v & bit) != 0) x ^= v;
dp[mask | (1<<i)] =
else y ^= v;
min(dp[mask | (1<<i)],
}
dp[mask] + cost[i])
return new int[]{x, y};
▶ Traveling Salesman }

dp[mask][u] =
min over v in mask: 4️⃣ Count Set Bits
dp[mask ^ (1<<u)][v] + int c = [Link](x);
dist[v][u] int c2 = [Link](y);

7️⃣ LIS (Important Pattern) 5️⃣ XOR from 1 to N

dp[i] = 1 + max(dp[j]) for all j<i static long xor1toN(long n) {
with a[j]<a[i] if (n % 4 == 0) return n;
if (n % 4 == 1) return 1;
Optimized:​ if (n % 4 == 2) return n + 1;
tails[k] = min ending value of LIS return 0;
length k }

8️⃣ Counting DP (Mod)​

dp[i] = (dp[i] + dp[j]) % MOD 6️⃣ Subarrays with XOR = K
static long countXorSubarrays(int[]

⚙️ BIT MANIPULATION — JAVA

​ a, int k) {
HashMap<Integer, Integer> map =
IMPLEMENTATIONS​
new HashMap<>();
1️⃣ Power of Two​
[Link](0, 1);
static boolean isPowerOfTwo(long x)
{​
int pref = 0;
return x > 0 && (x & (x - 1)) ==
long ans = 0;
0;​
}​
for (int v : a) {
​
2️⃣ Single Number (others twice)​ pref ^= v;
static int singleNumber(int[] a) {​ ans += [Link](pref
int x = 0;​ ^ k, 0);
for (int v : a) x ^= v;​ [Link](pref,
return x;​ [Link](pref, 0) + 1);
} }
return ans;
}
3️⃣ Two Unique Numbers (others twice)
static int[] twoUnique(int[] a) {
7️⃣ Maximum XOR Pair (Binary Trie)
int xr = 0;
for (int v : a) xr ^= v; static class Trie {
 Trie[] ch = new Trie[2]; for (int y : cur) [Link](y &
} x); // OR: y | x
cur = next;
static void insert(Trie root, int x)
{ for (int v : cur) {
Trie cur = root; // count / compare v
for (int i = 31; i >= 0; i--) { }
int b = (x >> i) & 1; }
if ([Link][b] == null)
[Link][b] = new Trie(); 9️⃣ Bitmask DP Template
cur = [Link][b];
int N = 1 << n;
}
int[] dp = new int[N];
}
[Link](dp, INF);
dp[0] = 0;
static int maxXor(Trie root, int x)
{
for (int mask = 0; mask < N; mask++)
Trie cur = root;
{
int ans = 0;
for (int i = 0; i < n; i++) {
for (int i = 31; i >= 0; i--) {
if ((mask & (1 << i)) == 0)
int b = (x >> i) & 1;
{
if ([Link][1 - b] != null) {
int nmask = mask | (1 <<
ans |= (1 << i);
i);
cur = [Link][1 - b];
dp[nmask] =
} else {
[Link](dp[nmask], dp[mask] +
cur = [Link][b];
cost[i]);
}
}
}
}
return ans;
}
}

🔟 SOS DP (Advanced)
Usage:​ int N = 1 << n;
Trie root = new Trie();​
int[] dp = new int[N];
for (int x : a) insert(root, x);​
int res = 0;​
// dp[mask] initialized with base
for (int x : a) res = [Link](res,
values
maxXor(root, x));

for (int i = 0; i < n; i++) {

8️⃣ AND / OR Subarray Trick for (int mask = 0; mask < N;
Set<Integer> cur = new HashSet<>(); mask++) {
long ans = 0; if ((mask & (1 << i)) != 0)
{
for (int x : a) { dp[mask] += dp[mask ^ (1
Set<Integer> next = new << i)];
HashSet<>(); }
[Link](x); }
}
1️⃣1️⃣ Linear XOR Basis ( 🔥 VERY IMPORTANT) [Link](a, b) // double
static class XorBasis { (avoid in mod problems)​
static final int LOG = 60; [Link](x)​
long[] basis = new long[LOG]; [Link](x)​
[Link](x)​
[Link](x)​
⚠️ Prefer manual power for mod, not
void insert(long x) {
for (int i = LOG - 1; i >=
0; i--) { [Link].
if (((x >> i) & 1) == 0)
continue; 🧠 BIT OPERATIONS (Integer / Long)
if (basis[i] == 0) {
basis[i] = x; [Link](x)​
return; [Link](x)​
} [Link](x)​
x ^= basis[i]; [Link](x)​
} [Link](x)​
} [Link](x)

long getMax() { 👉 VERY useful shortcuts:​

long res = 0; int msb = 31 -
for (int i = LOG - 1; i >= [Link](x);​
0; i--) { int lsb =
res = [Link](res, res [Link](x);
^ basis[i]);
}
return res;
📦 ARRAYS ([Link])​
[Link](arr)​
} [Link](arr, value)​
} [Link](arr, key)​
[Link](a, b)​
⚠️ JAVA BIT PITFALLS (MEMORIZE) [Link](arr, n)

●​
●​
Use 1L << i for i ≥ 31
Prefer int for masks, long for XOR
📚 COLLECTIONS
([Link])​
sums
[Link](list)​
●​ HashMap<Integer,Integer> faster
than Long [Link](list)​
●​ Bitmask DP max n ≈ 20 [Link](list)​
[Link](list)​
[Link](list, x)
JAVA INBUILT FUNCTIONS (CP CHEAT
SHEET) 🗂️ MAPS & SETS​
HashMap​
🔢 MATH ([Link]) [Link](k, 0)​
[Link](k, v)​
[Link](x)​ [Link](k, 1, Integer::sum)​
[Link](a, b)​ [Link](k)​
[Link](a, b)​ ​
TreeMap / TreeSet (ordered)​ [Link](a, (x, y) -> x[0] -
firstKey(), lastKey()​ y[0]);
floorKey(x), ceilingKey(x)​
lowerKey(x), higherKey(x)​ // fast swap​
​ a ^= b; b ^= a; a ^= b;​
🧵 STRING ([Link])​ ​
[Link]()​ Sort int[][] by first column
[Link](i)​ (ascending)​
[Link](l, r)​ [Link](arr, (a, b) ->
[Link](t)​ [Link](a[0], b[0]));​
[Link](t)​ ​
[Link]() Sort int[][] by first column
(descending)​

✂️ STRINGBUILDER​ [Link](arr, (a, b) ->

[Link](b[0], a[0]));
StringBuilder sb = new
StringBuilder();​
Given an integer array nums, return true if
[Link](x);​ you can partition the array into two subsets
[Link](0); // clear​ such that the sum of the elements in both
subsets is equal or false otherwise.
[Link]();
int n=[Link];
🧮 PRIORITY QUEUE​ int sum=0;
for(int i=0;i<n;i++)
PriorityQueue<Integer> pq = new sum+=nums[i];
PriorityQueue<>(); // min heap​ if(sum%2==1) return false;
sum=sum/2;
PriorityQueue<Integer> pq = new
boolean dp[][]=new
PriorityQueue<>([Link] boolean[n][sum+1];
rder()); //​ for(int i=0;i<n;i++)
dp[i][0]=true;
max heap
if(nums[0]<=sum)
dp[0][nums[0]]=true;
Custom:​ for(int i=1;i<n;i++)
PriorityQueue<int[]> pq = new {
for(int j=1;j<=sum;j++)
PriorityQueue<>((a, b) -> a[0] - {
b[0]); if(j<nums[i])
dp[i][j]=dp[i-1][j];

🚶 QUEUES & DEQUES​

else
dp[i][j]=dp[i-1][j] ||
dp[i-1][j-nums[i]];
ArrayDeque<Integer> dq = new
}
ArrayDeque<>();​ }
[Link](x);​ return dp[n-1][sum];
[Link](x);​
You are given an array 'arr' of size 'n'
[Link]();​
containing positive integers and a target sum
[Link]();
'k'.

🧪 RANDOM (HASHING / STRESS)​ Find the number of ways of selecting the

elements from the array such that the sum of
Random rng = new Random();​
chosen elements is equal to the target 'k'.
[Link](n);​
​
// sort pairs​
Since the number of ways can be very large, for(int j=0;j<=k;j++)
print it modulo 10 ^ 9 + 7.​ {
if(nums[i]>j)
int n=[Link]; dp[i][j]=dp[i-1][j];
int MOD = 1_000_000_007; else
long dp[][]=new dp[i][j]=dp[i-1][j] +
long[n][tar+1]; dp[i-1][j-nums[i]];
dp[0][0]=(num[0]==0)?2:1; }
if(num[0]!=0 && num[0]<=tar) }
dp[0][num[0]]=1; return dp[n-1][k];
for(int i=1;i<n;i++)
{ Input: amount = 5, coins = [1,2,5]
for(int j=0;j<=tar;j++) Output: 4
{ Explanation: there are four ways to make up
if(num[i]>j) the amount:
dp[i][j]=dp[i-1][j]%MOD; 5=5
else 5=2+2+1
dp[i][j]=(dp[i-1][j]+dp[i-1][j-num[i 5=2+1+1+1
]])%MOD; 5=1+1+1+1+1
} int n=[Link];
} int dp[][]=new
return (int)dp[n-1][tar]; int[n][amount+1];
for(int i=0;i<n;i++)
Input: nums = [1,1,1,1,1], target = 3 dp[i][0]=1;
Output: 5 for(int i=1;i<amount+1;i++)
Explanation: There are 5 ways to assign {
symbols to make the sum of nums be target if(i%coins[0]==0)

3. dp[0][i]=1;
}
-1 + 1 + 1 + 1 + 1 = 3
for(int i=1;i<n;i++)
+1 - 1 + 1 + 1 + 1 = 3
{
+1 + 1 - 1 + 1 + 1 = 3
for(int
+1 + 1 + 1 - 1 + 1 = 3
j=1;j<=amount;j++)
+1 + 1 + 1 + 1 - 1 = 3
{
int n=[Link];
if(coins[i]>j)
int sum=0;
dp[i][j]=dp[i-1][j];
for(int i:nums) sum+=i;
else
if((sum+target)%2==1) return
dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]
0;
];
int k=(sum+target)/2;
}
if(k<0) return 0;
}
int dp[][]=new int[n][k+1];
return dp[n-1][amount];
dp[0][0]=nums[0]==0?2:1;
if(nums[0]!=0 && nums[0]<=k)
dp[0][nums[0]]=1; You are given an integer array coins
for(int i=1;i<n;i++) representing coins of different denominations
{ and an integer amount representing a total
amount of money.
Return the fewest number of coins that you if(i+1>j)
need to make up that amount. If that amount dp[i][j]=dp[i-1][j];
of money cannot be made up by any else
combination of the coins, return -1. dp[i][j]=[Link](dp[i-1][j],price[i
]+dp[i][j-(i+1)]);
You may assume that you have an infinite }
number of each kind of coin. }
return dp[n-1][k];
int n=[Link];
int dp[][]=new
int[n][amount+1];
int INF=amount+1;
for(int i=0;i<n;i++)
dp[i][0]=0;
for(int j=1; j<=amount; j++)
if(j % coins[0] == 0)
dp[0][j] = j / coins[0];
else dp[0][j]=INF;
for(int i=1;i<n;i++)
{
for(int
j=1;j<=amount;j++)
{
if(coins[i]>j)
dp[i][j]=dp[i-1][j];
else
dp[i][j]=[Link](dp[i-1][j],1+dp[i]
[j-coins[i]]);
}
}
return dp[n-1][amount]>=INF
? -1 : dp[n-1][amount];

Rodcutting​
int n=[Link];
int dp[][]=new int[n][k+1];
for(int i=0;i<n;i++)
dp[i][0]=0;
for(int i=0;i<=k;i++)
{
dp[0][i]=i*price[0];
}
for(int i=1;i<n;i++)
{
for(int j=1;j<=k;j++)
{