import java.util.*;
class Node {
int val;
Node left, right;
Node(int v) {
val = v;
}
}
class Pair {
Node node;
int hd;
Pair(Node n, int h) {
node = n;
hd = h;
}
}
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) return;
int N = sc.nextInt(); // levels
int size = (int) Math.pow(2, N) - 1;
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
if (sc.hasNextInt()) {
arr[i] = sc.nextInt();
} else {
arr[i] = -1; // missing input handled
}
}
Node root = buildTree(arr);
verticalTraversal(root);
}
static Node buildTree(int[] arr) {
if (arr.length == 0 || arr[0] == -1) return null;
Node root = new Node(arr[0]);
Queue<Node> q = new LinkedList<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < arr.length) {
Node curr = q.poll();
if (i < arr.length && arr[i] != -1) {
curr.left = new Node(arr[i]);
q.add(curr.left);
}
i++;
if (i < arr.length && arr[i] != -1) {
curr.right = new Node(arr[i]);
q.add(curr.right);
}
i++;
}
return root;
}
static void verticalTraversal(Node root) {
if (root == null) return;
TreeMap<Integer, List<Integer>> map = new TreeMap<>();
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(root, 0));
while (!q.isEmpty()) {
Pair p = q.poll();
Node node = p.node;
int hd = p.hd;
map.putIfAbsent(hd, new ArrayList<>());
map.get(hd).add(node.val);
if (node.left != null) q.add(new Pair(node.left, hd - 1));
if (node.right != null) q.add(new Pair(node.right, hd + 1));
}
// print each vertical line separately
for (List<Integer> list : map.values()) {
for (int val : list) {
System.out.print(val + " ");
}
System.out.println();
}
}
}import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr1 = new int[n];
int[] arr2 = new int[n];
for (int i = 0; i < n; i++) arr1[i] = sc.nextInt();
for (int i = 0; i < n; i++) arr2[i] = sc.nextInt();
ArrayList<Integer> result = intersection(arr1, arr2);
System.out.println(result);
}
static ArrayList<Integer> intersection(int[] arr1, int[] arr2) {
HashMap<Integer, Integer> map = new HashMap<>();
ArrayList<Integer> ans = new ArrayList<>();
for (int num : arr1) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (int num : arr2) {
if (map.containsKey(num) && map.get(num) > 0) {
ans.add(num);
map.put(num, map.get(num) - 1);
}
}
Collections.sort(ans);
return ans;
}
}import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int l = sc.nextInt();
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < l; i++) {
set.add(sc.nextInt());
}
int q = sc.nextInt();
for (int i = 0; i < q; i++) {
int num = sc.nextInt();
if (set.contains(num)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
}
}import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long k = sc.nextLong();
int[] arr = new int[n];
HashMap<Integer, Integer> pos = new HashMap<>();
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
pos.put(arr[i], i);
}
for (int i = 0; i < n && k > 0; i++) {
int desired = n - i;
if (arr[i] != desired) {
int idx = pos.get(desired);
pos.put(arr[i], idx);
pos.put(desired, i);
int temp = arr[i];
arr[i] = arr[idx];
arr[idx] = temp;
k--;
}
}
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
HashMap<Integer, Integer> freq = new HashMap<>();
int maxFreq = 0, ans = arr[0];
for (int num : arr) {
int count = freq.getOrDefault(num, 0) + 1;
freq.put(num, count);
if (count > maxFreq) {
maxFreq = count;
ans = num;
}
}
System.out.println(ans);
}
}import java.util.*;
public class MergeKSortedArrays {
static class Pair implements Comparable<Pair> {
long val;
int row;
int col;
Pair(long val, int row, int col) {
this.val = val;
this.row = row;
this.col = col;
}
public int compareTo(Pair p) {
return Long.compare(this.val, p.val);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int K = sc.nextInt();
int N = sc.nextInt();
long[][] arr = new long[K][N];
for(int i = 0; i < K; i++)
for(int j = 0; j < N; j++)
arr[i][j] = sc.nextLong();
PriorityQueue<Pair> pq = new PriorityQueue<>();
for(int i = 0; i < K; i++)
pq.add(new Pair(arr[i][0], i, 0));
StringBuilder sb = new StringBuilder();
while(!pq.isEmpty()) {
Pair p = pq.poll();
sb.append(p.val).append(" ");
if(p.col + 1 < N)
pq.add(new Pair(arr[p.row][p.col + 1], p.row, p.col + 1));
}
System.out.println(sb.toString().trim());
}
}import java.util.*;
class Node {
int data;
Node left, right;
Node(int d) { data = d; }
}
class Pair {
Node node;
int hd;
Pair(Node n, int h) { node = n; hd = h; }
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
List<String> input = Arrays.asList(sc.nextLine().split(" "));
Queue<Node> queue = new LinkedList<>();
Node root = new Node(Integer.parseInt(input.get(0)));
queue.add(root);
int i = 1;
while(!queue.isEmpty() && i < input.size()) {
Node curr = queue.poll();
if(!input.get(i).equals("-1")) {
curr.left = new Node(Integer.parseInt(input.get(i)));
queue.add(curr.left);
}
i++;
if(i < input.size() && !input.get(i).equals("-1")) {
curr.right = new Node(Integer.parseInt(input.get(i)));
queue.add(curr.right);
}
i++;
}
Map<Integer,Integer> map = new TreeMap<>();
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(root,0));
while(!q.isEmpty()) {
Pair p = q.poll();
if(!map.containsKey(p.hd)) map.put(p.hd,p.node.data);
if(p.node.left!=null) q.add(new Pair(p.node.left,p.hd-1));
if(p.node.right!=null) q.add(new Pair(p.node.right,p.hd+1));
}
StringBuilder sb = new StringBuilder();
for(int val : map.values()) sb.append(val).append(" ");
System.out.println(sb.toString().trim());
}
}import java.util.*;
class Node {
int data;
Node left, right;
Node(int d) { data = d; }
}
class Pair {
Node node;
int hd;
Pair(Node n, int h) { node = n; hd = h; }
}
public class BottomViewBinaryTree {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
List<String> input = Arrays.asList(sc.nextLine().split(" "));
Queue<Node> queue = new LinkedList<>();
Node root = new Node(Integer.parseInt(input.get(0)));
queue.add(root);
int i = 1;
while(!queue.isEmpty() && i < input.size()) {
Node curr = queue.poll();
if(!input.get(i).equals("-1")) {
curr.left = new Node(Integer.parseInt(input.get(i)));
queue.add(curr.left);
}
i++;
if(i < input.size() && !input.get(i).equals("-1")) {
curr.right = new Node(Integer.parseInt(input.get(i)));
queue.add(curr.right);
}
i++;
}
Map<Integer,Integer> map = new TreeMap<>();
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(root,0));
while(!q.isEmpty()) {
Pair p = q.poll();
map.put(p.hd,p.node.data);
if(p.node.left!=null) q.add(new Pair(p.node.left,p.hd-1));
if(p.node.right!=null) q.add(new Pair(p.node.right,p.hd+1));
}
StringBuilder sb = new StringBuilder();
for(int val : map.values()) sb.append(val).append(" ");
System.out.println(sb.toString().trim());
}
}import java.util.*;
public class KthLargestElement {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int num : arr) {
pq.add(num);
if(pq.size() > k) pq.poll();
}
System.out.println(pq.peek());
}
}import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int n = sc.nextInt();
List<Employee> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
String name = sc.next();
int salary = sc.nextInt();
if (salary >= x) list.add(new Employee(name, salary));
}
Collections.sort(list, (a, b) -> {
if (b.salary != a.salary) return b.salary - a.salary;
return a.name.compareTo(b.name);
});
for (Employee e : list) {
System.out.println(e.name + " " + e.salary);
}
}
}
class Employee {
String name;
int salary;
Employee(String n, int s) {
name = n;
salary = s;
}
}import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int q = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
PriorityQueue<Long> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
int type = Integer.parseInt(st.nextToken());
if (type == 1) {
long x = Long.parseLong(st.nextToken());
long y = Long.parseLong(st.nextToken());
long dist = x * x + y * y;
if (maxHeap.size() < k) {
maxHeap.add(dist);
} else if (dist < maxHeap.peek()) {
maxHeap.poll();
maxHeap.add(dist);
}
} else {
sb.append(maxHeap.peek()).append("\n");
}
}
System.out.print(sb.toString());
}
}import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Map<Integer, Integer> freq = new HashMap<>();
for (int i = 0; i < n; i++) {
int num = arr[i];
freq.put(num, freq.getOrDefault(num, 0) + 1);
List<Integer> list = new ArrayList<>(freq.keySet());
Collections.sort(list, (a, b) -> {
if (!freq.get(a).equals(freq.get(b))) {
return freq.get(b) - freq.get(a); // higher freq first
}
return a - b; // smaller number first
});
int limit = Math.min(k, list.size());
for (int j = 0; j < limit; j++) {
System.out.print(list.get(j) + " ");
}
}
System.out.println();
}
}
}import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String[] arr = new String[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.next();
}
Arrays.sort(arr, (a, b) -> {
if (a.startsWith(b) || b.startsWith(a)) {
return b.length() - a.length();
}
return a.compareTo(b);
});
for (String s : arr) {
System.out.println(s);
}
}
}import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // left half
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // right half
for (int i = 0; i < n; i++) {
int num = arr[i];
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
// balance heaps
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.add(maxHeap.poll());
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.add(minHeap.poll());
}
// compute median
if (maxHeap.size() == minHeap.size()) {
System.out.print((maxHeap.peek() + minHeap.peek()) / 2 + " ");
} else {
System.out.print(maxHeap.peek() + " ");
}
}
System.out.println();
}
}
}import java.util.*;
public class Main {
static List<String> result = new ArrayList<>();
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
String num = sc.nextLine();
decode(num, 0, new StringBuilder());
Collections.sort(result);
for (String s : result) {
System.out.println(s);
}
}
static void decode(String num, int idx, StringBuilder sb) {
if (idx == num.length()) {
result.add(sb.toString());
return;
}
int one = num.charAt(idx) - '0';
if (one >= 1 && one <= 9) {
sb.append((char) ('A' + one - 1));
decode(num, idx + 1, sb);
sb.deleteCharAt(sb.length() - 1);
}
if (idx + 1 < num.length()) {
int two = (num.charAt(idx) - '0') * 10 + (num.charAt(idx + 1) - '0');
if (two >= 10 && two <= 26) {
sb.append((char) ('A' + two - 1));
decode(num, idx + 2, sb);
sb.deleteCharAt(sb.length() - 1);
}
}
}
}import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
int n = sc.nextInt();
int total = k * n;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < total; i++) {
pq.add(sc.nextInt());
}
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
}
}import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Map<Integer, Integer> freq = new HashMap<>();
for (int num : arr) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < k; i++) {
result.add(pq.poll()[0]);
}
Collections.sort(result);
for (int num : result) {
System.out.print(num + " ");
}
}
}