#pragma region opt #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma endregion opt #pragma region header #define _GNU_SOURCE #include #include #include #include #include #include #include #include #include #pragma endregion header #pragma region type /* signed integer */ typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef __int128_t i128; /* unsigned integer */ typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef __uint128_t u128; /* floating point number */ typedef float f32; typedef double f64; typedef long double f80; #pragma endregion type #pragma region macro #define MIN(a, b) (((a) < (b)) ? (a) : (b)) #define MAX(a, b) (((a) > (b)) ? (a) : (b)) #define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b))) #define POPCNT32(a) __builtin_popcount((a)) #define POPCNT64(a) __builtin_popcountll((a)) #define CTZ32(a) __builtin_ctz((a)) #define CLZ32(a) __builtin_clz((a)) #define CTZ64(a) __builtin_ctzll((a)) #define CLZ64(a) __builtin_clzll((a)) #define HAS_SINGLE_BIT32(a) (__builtin_popcount((a)) == (1)) #define HAS_SINGLE_BIT64(a) (__builtin_popcountll((a)) == (1)) #define MSB32(a) ((31) - __builtin_clz((a))) #define MSB64(a) ((63) - __builtin_clzll((a))) #define BIT_WIDTH32(a) ((a) ? ((32) - __builtin_clz((a))) : (0)) #define BIT_WIDTH64(a) ((a) ? ((64) - __builtin_clzll((a))) : (0)) #define LSBit(a) ((a) & (-(a))) #define CLSBit(a) ((a) & ((a) - (1))) #define BIT_CEIL32(a) ((!(a)) ? (1) : ((POPCNT32(a)) == (1) ? ((1u) << ((31) - CLZ32((a)))) : ((1u) << ((32) - CLZ32(a))))) #define BIT_CEIL64(a) ((!(a)) ? (1) : ((POPCNT64(a)) == (1) ? ((1ull) << ((63) - CLZ64((a)))) : ((1ull) << ((64) - CLZ64(a))))) #define BIT_FLOOR32(a) ((!(a)) ? (0) : ((1u) << ((31) - CLZ32((a))))) #define BIT_FLOOR64(a) ((!(a)) ? (0) : ((1ull) << ((63) - CLZ64((a))))) #define _ROTL32(x, s) (((x) << ((s) % (32))) | (((x) >> ((32) - ((s) % (32)))))) #define _ROTR32(x, s) (((x) >> ((s) % (32))) | (((x) << ((32) - ((s) % (32)))))) #define ROTL32(x, s) (((s) == (0)) ? (x) : ((((i64)(s)) < (0)) ? (_ROTR32((x), -(s))) : (_ROTL32((x), (s))))) #define ROTR32(x, s) (((s) == (0)) ? (x) : ((((i64)(s)) < (0)) ? (_ROTL32((x), -(s))) : (_ROTR32((x), (s))))) #define _ROTL64(x, s) (((x) << ((s) % (64))) | (((x) >> ((64) - ((s) % (64)))))) #define _ROTR64(x, s) (((x) >> ((s) % (64))) | (((x) << ((64) - ((s) % (64)))))) #define ROTL64(x, s) (((s) == (0)) ? (x) : ((((i128)(s)) < (0)) ? (_ROTR64((x), -(s))) : (_ROTL64((x), (s))))) #define ROTR64(x, s) (((s) == (0)) ? (x) : ((((i128)(s)) < (0)) ? (_ROTL64((x), -(s))) : (_ROTR64((x), (s))))) #pragma endregion macro #pragma region io int read_int(void) { // -2147483648 ~ 2147483647 (> 10 ^ 9) int c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } i32 in_i32(void) { // -2147483648 ~ 2147483647 (> 10 ^ 9) i32 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } u32 in_u32(void) { // 0 ~ 4294967295 (> 10 ^ 9) u32 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } i64 in_i64(void) { // -9223372036854775808 ~ 9223372036854775807 (> 10 ^ 18) i64 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } u64 in_u64(void) { // 0 ~ 18446744073709551615 (> 10 ^ 19) u64 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } static inline void write_int_inner(int x) { if (x >= 10) write_int_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void write_int(int x) { if (x < 0) { putchar_unlocked('-'); x = -x; } write_int_inner(x); } static inline void out_i32_inner(i32 x) { if (x >= 10) out_i32_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void out_i32(i32 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i32_inner(x); } void out_u32(u32 x) { if (x >= 10) out_u32(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void out_i64_inner(i64 x) { if (x >= 10) out_i64_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void out_i64(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i64_inner(x); } void out_u64(u64 x) { if (x >= 10) out_u64(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } void NL(void) { putchar_unlocked('\n'); } void SP(void) { putchar_unlocked(' '); } void write_int_array(int *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i) SP(); write_int(a[i]); } NL(); } void out_i32_array(i32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i) SP(); out_i32(a[i]); } NL(); } void out_u32_array(u32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i) SP(); out_u32(a[i]); } NL(); } void out_i64_array(i64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i) SP(); out_i64(a[i]); } NL(); } void out_u64_array(u64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i) SP(); out_u64(a[i]); } NL(); } #pragma endregion io #pragma region hash map #define USED_LAST 16383 u64 m_used[1 << 14]; u64 m_keys[1 << 20]; u64 m_vals[1 << 20]; u64 r = 11995408973635179863ull; static inline void hash_init(void) { memset(m_used, 0, (1 << 14) * sizeof(u64)); memset(m_keys, 0, (1 << 20) * sizeof(u64)); memset(m_vals, 0, (1 << 20) * sizeof(u64)); } static inline u32 hash(const u64 a) { return (u32)((a * r) >> 44); } static inline bool test_bit(u32 i) { return (1ull) & (m_used[USED_LAST - (i >> 6u)] >> (i & 63)); } static inline void set_bit(u32 i) { m_used[USED_LAST - (i >> 6)] |= (1ull << (i & 63)); } u64 get_value(u64 key) { for (u32 i = hash(key);; ++i, i &= 1048575) { if (!test_bit(i)) return 0; if (m_keys[i] == key) return m_vals[i]; } } void set_key_and_value(u64 key, u64 value) { for (u32 i = hash(key);; ++i, i &= 1048575) { if (!test_bit(i)) { set_bit(i); m_keys[i] = key; m_vals[i] = value; return; } if (m_keys[i] == key) { m_vals[i] = value; return; } } } void succ_value(u64 key) { for (u32 i = hash(key);; ++i, i &= 1048575) { if (!test_bit(i)) { set_bit(i); m_keys[i] = key; m_vals[i] = 1; return; } if (m_keys[i] == key) { m_vals[i]++; return; } } } void decl_value(u64 key) { for (u32 i = hash(key);; ++i, i &= 1048575) { if (!test_bit(i)) { return; } if (m_keys[i] == key) { m_vals[i]--; return; } } } #undef USED_LAST #pragma endregion hash map void Main(void) { hash_init(); int n = read_int(); int m = read_int(); for (int _ = 0; _ < n; ++_) succ_value(in_u64()); for (int _ = 0; _ < m; ++_) { out_u64(get_value(in_u64())); putchar_unlocked((_ == m - 1) ? '\n' : ' '); } } int main(void) { Main(); return 0; }